#include<bits/stdc++.h>
using namespace std;
int read() {
	char ch=getchar();int res=0,fl=1;
	while(ch<'0'||ch>'9'){if(ch=='-') fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
	return res*fl;
}
const int N=10;
const int M=184756;
const int mod=10007;
const int inf=1000000000;
int n,m;
int dp[1<<(N+N)],f[N+1][1<<(N+N)],__total,a[M],up[1<<(N+N)],down[1<<(N+N)];
int pos[1<<(N+N)][N+1],tp[1<<(N+N)],rk[1<<(N+N)][N+N];
void calc(int now) {
	for(int idx=0;idx<__total;++idx) {
		int s=a[idx];
		/*f[0][s]=dp[s];
		for(int k=1;k<n+m;++k) {;
			f[k][s]=f[k-1][s]+(((s&(1<<k))&&!(s&(1<<(k-1))))?f[k+((s>>(k+1))&1)][s^(3<<(k-1))]:0);
		}
		dp[s]=((up[s]<=now&&down[s]>now)*f[n+m-1][s])%mod;*/
		f[0][s]=dp[s];
		for(int j=1;j<=tp[s];++j) {
			int k=pos[s][j],t=s^(3<<(k-1));
			f[j][s]=f[j-1][s]+f[rk[t][k+((s>>(k+1))&1)]][t];
		}
		dp[s]=((up[s]<=now&&down[s]>now)*f[tp[s]][s])%mod;
	}
	return ;
}
int e[N][N];
string tmp;
void print(int s) {
	printf("(");
	for(int i=0;i<n+m;++i) printf("%d ",(s>>i)&1);
	printf(")");
	return ;
}
int test_case=0;
void gen() {
	test_case++;
	cin>>n>>m;
	for(int i=0;i<n;++i) {
		cin>>tmp;
		for(int j=0;j<m;++j) e[i][j]=(tmp[j]=='.')?0:(tmp[j]-'a'+1);
	}
	memset(up,0,sizeof(up));
	memset(down,60,sizeof(down));
	__total=0;
	for(int s=0;s<(1<<(n+m));++s) {
		if(__builtin_popcount(s)!=n) continue;
		a[__total++]=s; 
	}
	for(int idx=0;idx<__total;++idx) {
		int s=a[idx];
		for(int i=0;i<n+m-1;++i) 
			if(!(s&(1<<i))&&(s&(1<<(i+1)))) {
				int x,y,j;
				for(x=n,y=0,j=0;j<=i;++j) //n!!
					if(s&(1<<j)) x--;
					else y++;
				y--;x--;
				up[s]=max(up[s^(3<<i)],(e[x][y]>0)?e[x][y]:0);
				//if(s==5) printf("(%d,%d)\n",x,y);
				break;
			}
	}
	for(int idx=__total-1;idx>=0;--idx) {
		int s=a[idx];
		for(int i=0;i<n+m-1;++i) 
			if((s&(1<<i))&&!(s&(1<<(i+1)))) {
				int x,y,j;
				for(x=n,y=0,j=0;j<=i;++j) //n!!
					if(s&(1<<j)) x--;
					else y++;
				//y++;x++;不动了，这就是左上角!!
				down[s]=min(down[s^(3<<i)],(e[x][y]>0)?e[x][y]:inf);
				break;
			}
	}
	memset(tp,0,sizeof(tp));
	for(int idx=0;idx<__total;++idx) {
		int s=a[idx];
		for(int i=0;i<n+m-1;++i) 
		if(!(s&(1<<i))&&(s&(1<<(i+1)))) {
		pos[s][++tp[s]]=i+1;
		rk[s][i+1]=rk[s][i]+1;
	    }
	    else rk[s][i+1]=rk[s][i];
	}
	memset(dp,0,sizeof(dp));
	dp[(1<<n)-1]=1;
	for(int i=1;i<=26;++i) {;
		calc(i);
	}
	cout<<"Case #"<<test_case<<": "<<dp[((1<<n)-1)<<m]<<"\n";
	return ;
}
int main()
{
	//freopen("qoj5810.in","r",stdin);
	//freopen("qoj5810.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
		gen();
	return 0;
}