题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2895

/**==========================================*   This is a solution for ACM/ICPC problem**   @source：uva 11795 - Mega Man's Mission*   @type:  dp*   @author: wust_ysk*   @blog:  http://blog.csdn.net/yskyskyer123*   @email: 2530094312@qq.com*===========================================*/
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ysk(x)  (1<<(x))
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int maxn=16   ;
int n;
char s[maxn+5];
int ab[maxn+5];ll dp[2][ ysk(maxn)];
int Can[2][ ysk(maxn)];int ed,kase=0;void getab(int ind)
{scanf("%s",s);int & ans=ab[ind];ans=0;for(int i=0;s[i];i++){if(s[i]=='1') ans|=ysk(i);}}
void pre()
{scanf("%s",s);int can=0;for(int i=0;s[i];i++){if(s[i]=='1')   can|= ysk(i);}for(int i=0;i<n;i++){getab(i);}memset(dp,0,sizeof dp);memset(Can,0,sizeof Can);//我艹memset(ab,0,sizeof ab);dp[0][0]=1;Can[0][0]=can;ed=ysk(n)-1;}void DP()
{int now= 0,nex= 1;int m=n;int i,s;while(m--){for( i=0;i<n;i++){for( s=0;s<=ed;s++)  if(dp[now][s]&& !(s&ysk(i) ) && (Can[now][s]&ysk(i) )  ){int y=s|ysk(i);if(!dp[nex][y])  Can[nex][y]=Can[now][s]|ab[i];dp[nex][y]+=dp[now][s];}}memset(dp[now],0,sizeof dp[now]);now^=1,nex^=1;}printf("Case %d: %lld\n",++kase,dp[now][ed]);}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);pre();DP();}return 0;
}