#include <iostream>

#include <cstdio>

#include <set>

#define maxn 0x3f3f3f

using namespace std;

int f[][];

char m[][];

int main()

{

//    freopen("in.txt","r",stdin);

    int t;

    cin>>t;

    while(t--)

    {

        int n,d,ans=;

        cin>>n>>d;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(i==j) f[i][j]=;

                else f[i][j]=maxn;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            {

                cin>>m[i][j];

                if(m[i][j]=='Y') f[i][j]=d;

            }

        for(int k=;k<=n;k++)

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                {

                    if(f[i][j]>f[i][k]+f[k][j])

                        f[i][j]=f[i][k]+f[k][j];

                }

        int flag=;

        for(int i=;i<=n;i++)

            for(int j=i+;j<=n;j++)

            {

                if(f[i][j]==maxn)

                {

                    flag=;

                    break;

                }

                else ans=max(f[i][j],ans);

            }

        if(flag) cout<<ans<<endl;

        else cout<<"-1"<<endl;

    }

}