#include<bits/stdc++.h>
using namespace std;
const int N=55;
int f[N][N][15],a[N][N][N][N];
char g[N][N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                cin>>g[i][j];
            }
        }
        //memset(f,0,sizeof f);
        memset(a,0,sizeof a);

        if(g[1][1]!='H') f[1][1][0]=2;
        int dx[2]={1,0};
        int dy[2]={0,1};
        a[1][1][0][0]=a[1][1][0][1]=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(g[i][j]=='H')continue;
                for(int i1=0;i1<=k;++i1)
                {
                    for(int j1=0;j1<2;++j1)
                    {
                        int x=i+dx[j1];
                        int y=j+dy[j1];
                        if(x>n||y>n||g[x][y]=='H') continue;
                        a[x][y][i1][j1]+=a[i][j][i1][j1];
                        if((x==1||y==1)&&i1==0) continue;
                        if(i1+1<=k) 
                        {
                            a[x][y][i1+1][j1]+=a[i][j][i1][j1^1];
                        }
                    //cout<<a[i][j][i1][0]<<" "<<a[i][j][i1][1]<<endl;
                    }
                }
            }
        
        }
        int res=0;
            for(int i1=0;i1<=k;++i1)
            {
                res+=a[n][n][i1][0]+a[n][n][i1][1];
            }
            cout<<res<<endl;
    }

    return 0;
}