求调，闭关！！！

#include<bits/stdc++.h>
#define ll long long
#define INF 1e8
using namespace std;
int T;
int g[55][55];
priority_queue<pair<int, int>> q;
int dist[55];
bool vis[55];
int dp[55][55];
int n, d;
void floyd()
{
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (g[i][j]) dp[i][j] = g[i][j];
			else dp[i][j] = INF;
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
}
int main(){
	cin >> T;
	while(T--){
		cin >> n >> d;
		char a[55][55];
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++) cin >> a[i][j];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				g[i][j] = 0;
			}
		}
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++){
				if(a[i][j] == 'Y'){
					g[i][j] = d;
				}
			}
		bool flag = 0;
		int ans = -INF;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(g[i][j] != 0) {
					flag = 1;
					break;
				}
			}
		}
		if(flag == 0){
			cout << -1 << endl;
			continue;
		}
		floyd();
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(dp[i][j] != INF) ans = max(ans, dp[i][j]);
			}
		}
		cout << ans << endl;
	}
	return 0;
}