#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+N][1<<(N+N)],__total,a[M],up[1<<(N+N)],down[1<<(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];
			if((s&(1<<k))&&!(s&(1<<(k-1)))) {
				(f[k][s]+=f[k+((s>>(k+1))&1)][s^(3<<(k-1))])%=mod;
		//		if(now==4&&s==12) printf("(%d,%d)   ",s^(3<<(k-1)),f[k+((s>>(k+1))&1)][s^(3<<(k-1))]);//注意，如果下一位是1,011->101产生新下凸，这个下凸要越过
			}
		}
	//	if(now==4&&s==12) printf("*\n*\n");
		dp[s]=(up[s]<=now&&down[s]>now)*f[n+m-1][s];
	}
	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(dp,0,sizeof(dp));
	dp[(1<<n)-1]=1;
	for(int i=1;i<=26;++i) {
		calc(i);
	/*	for(int idx=0;idx<__total;++idx) {
			print(a[idx]);printf(" %d\n",dp[a[idx]]);
			for(int k=0;k<n+m;++k) printf("%d,",f[k][a[idx]]);
			printf("\n\n");
		}
		printf("\n\n\n\n");*/
	}
	//printf("%d\n",dp[((1<<n)-1)<<m]);
	cout<<"Case #"<<test_case<<": "<<dp[((1<<n)-1)<<m]<<"\n";
/*	for(int i=0;i<n;++i) {
		for(int j=0;j<m;++j) printf("%d",e[i][j]);
		printf("\n");
	}
	for(int idx=0;idx<__total;++idx) {
		print(a[idx]);
		printf("(%d,%d)\n",up[a[idx]],down[a[idx]]);
	}*/
	return ;
}
int main()
{
	//freopen("qoj5810.in","r",stdin);
	//freopen("qoj5810.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
		gen();
	return 0;
}