#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50+10;
const int INF=0x3f3f3f3f;
int t,n,k,ans;
char a[N][N];
void dfs(int x,int y,int sum,int fx){
	if(sum>k)return;
	if(x==n&&y==n){
		ans++;
		return;
	}
	if(y+1<=n&&a[x][y+1]=='.'){
		dfs(x,y+1,sum+(fx==2),1);
	}
	if(x+1<=n&&a[x+1][y]=='.'){
		dfs(x+1,y,sum+(fx==1),2);
	}
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>a[i][j];
			}
		}
		dfs(1,1,0,0);
		cout<<ans<<endl;
		ans=0;
	}
    return 0;
}