rt

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
char a[58][58];
bool vis[58][58];
void dfs(int x,int y,int cnt,char f){
	vis[x][y]=1;
	if(x==n&&y==n){
		if(cnt<=k){
			ans++;
		}
		vis[x][y]=0;
		return ;
	}
	if(x+1<=n){ 
		if(vis[x+1][y]==0){
			if(f=='R'&&cnt<k) dfs(x+1,y,cnt+1,'D');
			if(f!='R') dfs(x+1,y,cnt,'D');
		}
	}
	if(y+1<=n){
		if(vis[x][y+1]==0){
			if(f=='D'&&cnt<k) dfs(x,y+1,cnt+1,'R');
			if(f!='D') dfs(x,y+1,cnt,'R');
		}
	}
	vis[x][y]=0;
	return ;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(a,'N',sizeof(a));
		memset(vis,0,sizeof(vis));
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				char x;
				cin>>x;
				a[i][j]=x;
				if(a[i][j]=='H') vis[i][j]=1;
			}
		}
		ans=0;
		dfs(1,1,0,'N');
		cout<<ans<<"\n";
	}
	return 0;
}