#include<bits/stdc++.h>

using namespace std;

const int N = 10 + 5, K = 30, S = 2e5 + 5, Mod = 10007;

inline void upd(int &x, int dx){
	x = x + dx;
	if(x >= Mod) x -= Mod;
}

array<int, N> tmp;

int n = 0, m = 0, tot = 0, dp[K][S][N] = {}, tr[S][N] = {};
char str[N][N] = {};
map<array<int, N> , int> id;
array<int, N> state[S] = {};

inline void dfs(int x){
	if(x <= n) for(int y = 0 ; y <= tmp[x - 1] ; y ++){
		tmp[x] = y;
		dfs(x + 1);
	}
	else{
		tot ++;
		id[tmp] = tot, state[tot] = tmp;
	}
}

inline void init(){
	n = m = tot = 0;
	memset(str, 0, sizeof(str));
	memset(dp, 0, sizeof(dp)), memset(tr, 0, sizeof(tr));
	map<array<int, N> , int>().swap(id);
	memset(state, 0, sizeof(state));
}

inline void solve(int cas){
	scanf("%d %d", &n, &m);
	for(int x = 1 ; x <= n ; x ++) scanf("%s", str[x] + 1);
	tmp.fill(0);
	tmp[0] = m;
	dfs(1);
	for(int s = 1 ; s <= tot ; s ++) for(int x = 1 ; x <= n ; x ++){
		tmp = state[s];
		if(tmp[x] < tmp[x - 1]){
			tmp[x] ++;
			tr[s][x] = id[tmp];
		}
	}
	dp[0][1][1] = 1;
	for(int k = 0 ; k < 26 ; k ++) for(int s = 1 ; s <= tot ; s ++){
		tmp = state[s];
		for(int x = 1 ; x <= n ; x ++){
			upd(dp[k][s][x + 1], dp[k][s][x]);
			if(tr[s][x]){
				int t = tr[s][x], y = tmp[x] + 1;
				if(str[x][y] == '.' || str[x][y] - 'a' == k) upd(dp[k][t][x], dp[k][s][x]);
			}
		}
		upd(dp[k + 1][s][1], dp[k][s][n + 1]);
	}
	printf("Case #%d: %d\n", cas, dp[26][tot][1]);
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 1 ; i <= T ; i ++) init(), solve(i);
	return 0;
}