【问题描述】

一个国家有 $N$ 个公民，标记为 $0，1，2，...，N-1$，每个公民有一个存款额。已知每个公民有一些朋友，同时国家有一条规定朋友间的存款额之差不能大于 $d$。也就是

说，$a$ 和 $b$ 是朋友的话，$a$ 有 $x$ 元的存款，$b$ 有 $y$ 元，那么 $|x-y|≤d$。给定 $d$ 值与 $N$ 个人的朋友关系，求这个国家最富有的人和最贫穷的人的存款相差最大的可能值是多少？

即求贫富差距的最大值的下界。若这个值为无穷大，输出 $-1$.

【输入格式】

多组测试数据，第一行一个整数 $T$，表示测试数据数量，$1≤T≤5$ 每组测试数据有相同的结构构成。

每组数据的第一行两个整数 $N，d$，表示人数与朋友间存款差的最大值，其中 $2≤N≤50，0≤d≤1000$。

接下来有一个 $N*N$ 的数组 $A$，若 $A[i][ j]='Y'$ 表示 $i$ 与 $j$ 两个人是朋友，否则 $A[i][ j]='N'$ 表示不是朋友。其中 $A[i][i]='N'$，且保证 $A[i][ j]=A[ j][i]$。

【输出格式】

每组数据一行输出，即这个国家的贫富差距最大值的下界，如果这个值为无穷大输出 $-1$。

【输入样例1】

3
3 10
NYN 
YNY 
NYN 
2 1 
NN 
NN
6 1000
NNYNNN 
NNYNNN 
YYNYNN 
NNYNYY 
NNNYNN 
NNNYNN

【输出样例1】

20
-1
3000