繁繁想和小伙伴们打游戏，游戏在一个山庄进行，这个山庄有N座山，编号为1到N，ji为了方便大家

在不同的山之间移动，繁繁建了一些桥，由于技术的原因，桥连接的两座山的高度差不能超过d，现

在已知这些桥，求这个山庄最高的山和最低的山差距最大是多少？如果差距可以为无穷大，输出-1。

输入格式

第一个一个数T，表示测试数据数量（T<=5,2<=N<=50,0<=d<=1000）

每组数据第一行两个数N和d

接下来一个N行N列的矩阵，第i行j列为Y表示i和j之间建了一座桥，否则表示没有建

保证第i行j列和第j行i列值相同，并且第i行第i列值为N

输出格式

T行，每行一个答案，若最大值可能为正无穷，输出-1

数据范围

对于20%的数据，T<=3,N<=40

对于50%的数据，T<=3

对于100%的数据，T<=5,2<=N<=50,0<=d<=1000

输入样例

3

3 10

NYN

YNY

NYN

2 1

NN

NN

6 1000

NNYNNN

NNYNNN

YYNYNN

NNYNYY

NNNYNN

NNNYNN

输出样例

20

-1

3000

样例解释

第一个样例，1和2之间不能超过d，2和3之间不能超过d，那么最大就是1和2差恰好为d，2和3差恰

好为d

第二个样例，1和2之间没有限制，那么他们之间可能差为正无穷