#include<bits/stdc++.h>
using namespace std;
//defines
#define openin freopen("input.txt","r",stdin)
#define openout freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define int long long
#define mod 1000000007
#define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
#define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
os << "(" ;
os << v.first << "," << v.second << ")" ;
return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
os << "[" ;
int sz = v.size() ;
for(int i = 0 ; i < sz ; ++i) {
os << v[i] ;
if(i!=sz-1)os << "," ;
}
os << "]\n" ;
return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
T last = *v.rbegin() ;
os << "[" ;
for(auto it : v) {
os << it ;
if(it != last) os << "," ;
}
os << "]\n" ;
return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
for(auto it : v) {
os << it.first << " : " << it.second << "\n" ;
}
return os ;
}
int power(int a , int b)
{
int res = 1 ;
while(b)
{
if(b%2) {
res = (res * a) % mod ;
}
b/=2 ;
a = (a*a) % mod ;
}
return res ;
}
//debug
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N = 111 ;
string arr[N] ;
string forbid[N] ;
int cnt[2][N] ;
int n , m , p ;
map<pair<int,vector<int> > , int> dp ;
int solve(int idx , vector<int> &temp) {
if(idx == p) {
if(temp.empty()) return 0 ;
return mod ;
}
if(dp.find({idx,temp}) != dp.end()) return dp[{idx,temp}] ;
int &res = dp[{idx,temp}] ;
vector<int> temp0 , temp1 ;
int j = 0 ;
while(j < temp.size() && forbid[temp[j]][idx] == '0') {
temp0.pb(temp[j]) ; ++j ;
}
while(j < temp.size() && forbid[temp[j]][idx] == '1') {
temp1.pb(temp[j]) ; ++j ;
}
res = solve(idx + 1 , temp0) + cnt[1][idx] ;
res = min(res , solve(idx + 1 , temp1) + cnt[0][idx]) ;
return res ;
}
int32_t main()
{
fast;
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin) ;
freopen("output.txt","w",stdout) ;
#endif // ONLINE_JUDGE
int t ; cin >> t ;
rep(tt,1,t) {
cin >> n >> m >> p ;
rep(i,1,n) cin >> arr[i] ;
rep(i,1,m) cin >> forbid[i] ;
memset(cnt , 0 , sizeof(cnt)) ;
rep(pos,0,p-1) {
rep(j,0,1) {
rep(i,1,n) {
cnt[j][pos] += (arr[i][pos] == ('0' + j)) ;
}
}
}
vector<pair<string,int> > bla ;
rep(i,1,m) bla.push_back({forbid[i],i}) ;
sort(all(bla)) ;
vector<int> temp ;
rep(i,0,m-1) temp.pb(bla[i].second) ;
int ans = solve(0,temp) ;
cout << "Case #" << tt << ": " << ans << endl ;
dp.clear() ;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vZGVmaW5lcwojZGVmaW5lIG9wZW5pbiBmcmVvcGVuKCJpbnB1dC50eHQiLCJyIixzdGRpbikKI2RlZmluZSBvcGVub3V0IGZyZW9wZW4oIm91dHB1dC50eHQiLCJ3IixzdGRvdXQpCiNkZWZpbmUgZmFzdCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApO2NvdXQudGllKDApCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgcmVwcihpLHgseSkgZm9yIChfX3R5cGVvZih4KSBpPXg7aT49eTtpLS0pCiNkZWZpbmUgcmVwKGkseCx5KSBmb3IgKF9fdHlwZW9mKHgpIGk9eDtpPD15O2krKykKI2RlZmluZSBhbGwoYykgKGMpLmJlZ2luKCksKGMpLmVuZCgpCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKCi8qIFByaW50IHBhaXIgKi8KdGVtcGxhdGUgPHR5cGVuYW1lIFQsdHlwZW5hbWUgUz4Kb3N0cmVhbSAmIG9wZXJhdG9yIDw8IChvc3RyZWFtICZvcyAsIGNvbnN0IHBhaXI8VCxTPiAmdikgewogICAgb3MgPDwgIigiIDsKICAgIG9zIDw8IHYuZmlyc3QgPDwgIiwiIDw8IHYuc2Vjb25kIDw8ICIpIiA7CiAgICByZXR1cm4gb3MgOwp9Ci8qIFByaW50IHZlY3RvciAqLwp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kb3N0cmVhbSAmIG9wZXJhdG9yIDw8IChvc3RyZWFtICZvcyAsIGNvbnN0IHZlY3RvcjxUPiAmdikgewogICAgb3MgPDwgIlsiIDsKICAgIGludCBzeiA9IHYuc2l6ZSgpIDsKICAgIGZvcihpbnQgaSA9IDAgOyBpIDwgc3ogOyArK2kpIHsKICAgICAgICBvcyA8PCB2W2ldIDsKICAgICAgICBpZihpIT1zei0xKW9zIDw8ICIsIiA7CiAgICB9CiAgICBvcyA8PCAiXVxuIiA7CiAgICByZXR1cm4gb3MgOwp9Ci8qIFByaW50IHNldCAqLwp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kb3N0cmVhbSAmIG9wZXJhdG9yIDw8IChvc3RyZWFtICZvcyAsIGNvbnN0IHNldDxUPiAmdikgewogICAgVCBsYXN0ID0gKnYucmJlZ2luKCkgOwogICAgb3MgPDwgIlsiIDsKICAgIGZvcihhdXRvIGl0IDogdikgewogICAgICAgIG9zIDw8IGl0ICA7CiAgICAgICAgaWYoaXQgIT0gbGFzdCkgb3MgPDwgIiwiIDsKICAgIH0KICAgIG9zIDw8ICJdXG4iIDsKICAgIHJldHVybiBvcyA7Cn0KLyogUHJpbnQgTWFwICovCnRlbXBsYXRlIDx0eXBlbmFtZSBULHR5cGVuYW1lIFM+Cm9zdHJlYW0gJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MgLCBjb25zdCBtYXA8VCxTPiAmdikgewogICAgZm9yKGF1dG8gaXQgOiB2KSB7CiAgICAgICAgb3MgPDwgaXQuZmlyc3QgPDwgIiA6ICIgPDwgaXQuc2Vjb25kIDw8ICJcbiIgOwogICAgfQogICAgcmV0dXJuIG9zIDsKfQppbnQgcG93ZXIoaW50IGEgLCBpbnQgYikKewogICAgaW50IHJlcyA9IDEgOwogICAgd2hpbGUoYikKICAgIHsKICAgICAgICBpZihiJTIpIHsKICAgICAgICAgICAgcmVzID0gKHJlcyAqIGEpICUgbW9kIDsKICAgICAgICB9CiAgICAgICAgYi89MiA7CiAgICAgICAgYSA9IChhKmEpICUgbW9kIDsKICAgIH0KICAgIHJldHVybiByZXMgOwp9CgovL2RlYnVnCiNkZWZpbmUgVFJBQ0UKCiNpZmRlZiBUUkFDRQojZGVmaW5lIHRyYWNlKC4uLikgX19mKCNfX1ZBX0FSR1NfXywgX19WQV9BUkdTX18pCnRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxPgp2b2lkIF9fZihjb25zdCBjaGFyKiBuYW1lLCBBcmcxJiYgYXJnMSl7CgkJY2VyciA8PCBuYW1lIDw8ICIgOiAiIDw8IGFyZzEgPDwgc3RkOjplbmRsOwp9CnRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxLCB0eXBlbmFtZS4uLiBBcmdzPgp2b2lkIF9fZihjb25zdCBjaGFyKiBuYW1lcywgQXJnMSYmIGFyZzEsIEFyZ3MmJi4uLiBhcmdzKXsKCQljb25zdCBjaGFyKiBjb21tYSA9IHN0cmNocihuYW1lcyArIDEsICcsJyk7Y2Vyci53cml0ZShuYW1lcywgY29tbWEgLSBuYW1lcykgPDwgIiA6ICIgPDwgYXJnMTw8IiB8ICI7X19mKGNvbW1hKzEsIGFyZ3MuLi4pOwp9CiNlbHNlCiNkZWZpbmUgdHJhY2UoLi4uKQojZW5kaWYKCmNvbnN0IGludCBOID0gMTExIDsKc3RyaW5nIGFycltOXSA7CnN0cmluZyBmb3JiaWRbTl0gOwppbnQgY250WzJdW05dIDsKaW50IG4gLCBtICwgcCA7Cm1hcDxwYWlyPGludCx2ZWN0b3I8aW50PiA+ICwgaW50PiBkcCA7CgppbnQgc29sdmUoaW50IGlkeCAsIHZlY3RvcjxpbnQ+ICZ0ZW1wKSB7CiAgICBpZihpZHggPT0gcCkgewogICAgICAgIGlmKHRlbXAuZW1wdHkoKSkgcmV0dXJuIDAgOwogICAgICAgIHJldHVybiBtb2QgOwogICAgfQogICAgaWYoZHAuZmluZCh7aWR4LHRlbXB9KSAhPSBkcC5lbmQoKSkgcmV0dXJuIGRwW3tpZHgsdGVtcH1dIDsKICAgIGludCAmcmVzID0gZHBbe2lkeCx0ZW1wfV0gOwogICAgdmVjdG9yPGludD4gdGVtcDAgLCB0ZW1wMSA7CiAgICBpbnQgaiA9IDAgOwogICAgd2hpbGUoaiA8IHRlbXAuc2l6ZSgpICYmIGZvcmJpZFt0ZW1wW2pdXVtpZHhdID09ICcwJykgewogICAgICAgIHRlbXAwLnBiKHRlbXBbal0pIDsgKytqIDsKICAgIH0KICAgIHdoaWxlKGogPCB0ZW1wLnNpemUoKSAmJiBmb3JiaWRbdGVtcFtqXV1baWR4XSA9PSAnMScpIHsKICAgICAgICB0ZW1wMS5wYih0ZW1wW2pdKSA7ICsraiA7CiAgICB9CiAgICByZXMgPSBzb2x2ZShpZHggKyAxICwgdGVtcDApICsgY250WzFdW2lkeF0gOwogICAgcmVzID0gbWluKHJlcyAsIHNvbHZlKGlkeCArIDEgLCB0ZW1wMSkgKyBjbnRbMF1baWR4XSkgOwogICAgcmV0dXJuIHJlcyA7Cn0KaW50MzJfdCBtYWluKCkKewogICAgZmFzdDsKICAgICNpZm5kZWYgT05MSU5FX0pVREdFCiAgICBmcmVvcGVuKCJCLmluIiwiciIsc3RkaW4pIDsKICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCJ3IixzdGRvdXQpIDsKICAgICNlbmRpZiAvLyBPTkxJTkVfSlVER0UKICAgIGludCB0IDsgY2luID4+IHQgOwogICAgcmVwKHR0LDEsdCkgewogICAgICAgIGNpbiA+PiBuID4+IG0gPj4gcCA7CiAgICAgICAgcmVwKGksMSxuKSBjaW4gPj4gYXJyW2ldIDsKICAgICAgICByZXAoaSwxLG0pIGNpbiA+PiBmb3JiaWRbaV0gOwogICAgICAgIG1lbXNldChjbnQgLCAwICwgc2l6ZW9mKGNudCkpIDsKICAgICAgICByZXAocG9zLDAscC0xKSB7CiAgICAgICAgICAgIHJlcChqLDAsMSkgewogICAgICAgICAgICAgICAgcmVwKGksMSxuKSB7CiAgICAgICAgICAgICAgICAgICAgY250W2pdW3Bvc10gKz0gKGFycltpXVtwb3NdID09ICgnMCcgKyBqKSkgOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHZlY3RvcjxwYWlyPHN0cmluZyxpbnQ+ID4gYmxhIDsKICAgICAgICByZXAoaSwxLG0pIGJsYS5wdXNoX2JhY2soe2ZvcmJpZFtpXSxpfSkgOwogICAgICAgIHNvcnQoYWxsKGJsYSkpIDsKICAgICAgICB2ZWN0b3I8aW50PiB0ZW1wIDsKICAgICAgICByZXAoaSwwLG0tMSkgdGVtcC5wYihibGFbaV0uc2Vjb25kKSA7CiAgICAgICAgaW50IGFucyA9IHNvbHZlKDAsdGVtcCkgOwogICAgICAgIGNvdXQgPDwgIkNhc2UgIyIgPDwgdHQgPDwgIjogIiA8PCBhbnMgPDwgZW5kbCA7CiAgICAgICAgZHAuY2xlYXIoKSA7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=