题目描述

有一个 R 行 C 列的二维数组 board ，如果board[i][j]= 'R' 则表示第 i 行第 j 列的格子是石头，如果 board[i][j]= '.' 则表示第 i 行第 j 列的格子是空地。

石头 A 和石头 B 是 冲突 的前提是同时满足如下的所有条件：

1. 石头 A 和石头 B 的颜色不同。
2. 石头 A 和石头 B 在同一行或者同一列。
3. 石头 A 与石头 B 之间没有其他的石头。

你要对所有的石头进行染色，但必须保证所有的石头都不能有 冲突 。在满足上述的所有条件的前提下，你希望用到的颜色种类越多越好，输出最多的颜色种类。

输入格式

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1 <= G <= 10。

每组测试数据格式如下：

第一行，两个整数 R 和 C 。 1 <= R,C <= 20。

接下来是 R 行 C 列的二维数组board。board[i][j]='R'或 '.'

输出格式

共 G 行，每行一个整数。

样例

3
3 4
.R.R
R.R.
.R.R
1 15
RRRRRRRRRRRRRRR
6 15
...............
...............
...............
...............
...............
...............

2
1
0