有一只特别的狼，它在每个夜晚会进行变色，研究发现这只狼的基因中存在一个变色矩阵，记为 colormap ，如果 colormap[i][j]='Y'则这只狼可以在某一个夜晚从颜色 i 变成颜色 j（一晚不可以变色多次），如果 colormap[i][j]='N' 则不能在一个晚上从 i 变成 j 色。

狼每次变色并不是随机变的，它有一定策略，在每个夜晚，如果它没法改变它的颜色，那么它就不变色，如果存在可改变的颜色，那它变为标号最小的颜色。

现在这只狼是颜色 0 ，你想让其变为颜色 N-1 ，你有一项技术可以改变狼的一些基因，具体说你可以花费 1 的代价，将狼的变色矩阵中的某一个  colormap[i][j]='Y' 改变成  colormap[i][j]=N' 。问至少花费多少总代价改变狼的基因，让狼按它的变色策略可以从颜色 0 经过若干天的变色变成颜色N-1。如果一定不能变成 N-1 ，则输出-1. 

多组测试数据，第一行一个整数 T ，表示测试数据数量， 1<T<5。

每组数据第一行一个整数 N， 2<=N<=50 ；

之后有 N 行，每行 N 个字符，表示狼的变色矩阵，矩阵中只有‘ Y ’与‘ N ’两种字符，第 i 行第 j 列的字符就是  colormap[i][j] 。

每组数据一行输出，即最小代价，无解时输出 -1。