#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::greater; using std::endl; const int MAXN(1 << 17); long long table[MAXN]; int can[MAXN]; int weapon[20]; char str[20]; int main() { int T, n_case(0); scanf("%d", &T); while(T--) { int n, tw = 0; scanf("%d%s", &n, str); for(int i = 0; i < n; ++i) if(str[i]-'0') tw |= 1 << i; for(int i = 0; i < n; ++i) { scanf("%s", str); weapon[i] = 0; for(int j = 0; j < n; ++j) if(str[j]-'0') { weapon[i] |= 1 << j; } } for(int i = 0; i < (1 << n); ++i) { can[i] = tw; for(int j = 0; j < n; ++j) if(i&(1 << j)) can[i] |= weapon[j]; } table[0] = 1LL; for(int i = 1; i < (1 << n); ++i) { table[i] = 0LL; for(int j = 0; j < n; ++j) if((i &(1 << j)) && (can[i^(1 << j)]&(1 << j))) table[i] += table[i^(1 << j)]; } printf("Case %d: %lld\n", ++n_case, table[(1 << n)-1]); } return 0; }