一张棋盘由 n 行 m 列的网格矩阵组成，每个网格中最多放一颗棋子。当前棋盘上已有若干棋子，所有水平方向或竖直方向上相邻的棋子属于同一连通块。 现给定棋盘上所有棋子的位置，如果要使棋盘上出现两个及以上的棋子连通块，请问最少需要移除几颗棋子？如果无论怎么移除棋子都无法满足要求，则输出 -1。 注：只能通过移除棋子的操作来使棋盘上出现两个及以上的棋子连通块。

示例说明： 如下方原始3×3棋盘（棋子位于(0,1)、(0,2)、(1,1)、(1,2)）所示，最少需要移除2颗棋子才能使棋盘上出现两个及以上的棋子连通块，移除后棋盘示意图如下：

原始3×3棋盘示意图：

输入格式

本题每个测试点包含多组测试数据：

1. 第一行包含一个整数 T(1 ≤ T ≤ 50)，表示数据组数。
2. 接下来 T 组数据，每组数据第一行输入两个整数 n 和 m(1 ≤ n, m ≤ 60)，分别表示棋盘的行数和列数，整数之间以一个空格隔开。
3. 接下来 n 行，每行输入 m 个大写字符（字符为 'G' 或 'L'），'G' 表示该位置有棋子，'L' 表示无棋子，字符之间以一个空格隔开。

输出格式

输出 T 行，每行一个整数，第 i 行的整数表示第 i 组数据的答案；如果无法满足要求，输出 -1。

输入样例

2
3 3
L G G
L G G
L L L
4 4
L L L L
L G L L
L G L L
L L L L

输出样例

2
-1