题目描述

Leo 有一个 $N$ 行 $M$ 列的网格。最初，每个格子都被涂成黑色或白色。

如果两个格子 $A$ 和 $B$ 共用一条边且颜色相同，或者存在一个格子 $C$ 同时与 $A$、$B$ 连通，那么称 $A$ 和 $B$ 连通。也就是说，颜色相同且能通过上下左右相邻格子互相到达的所有格子组成一个连通块。

Leo 想把整个网格涂成同一种颜色。他可以通过若干步完成这件事。每一步中，Leo 可以选择一个格子，并把所有与该格子连通的格子的颜色翻转（黑色变为白色，白色变为黑色）。

Leo 想知道，至少需要多少步才能使所有格子颜色相同。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $N,M$（$1\le N,M\le 40$）；
• 接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串。字符 X 表示黑色，字符 O 表示白色。

输出格式

对于每组测试数据，输出一行一个整数，表示使所有格子颜色相同所需的最少步数。

说明/提示

对于第二组样例，一种最优方案如下。

第 $1$ 步，翻转格子 $(2,2)$ 所在的连通块：

XOX
OOO
XOX

第 $2$ 步，翻转格子 $(1,2)$ 所在的连通块：

XXX
XXX
XXX

两步后，所有格子均为同一种颜色。

数据范围与约定

• 第一行包含两个整数 $N,M$（$1\le N,M\le 40$）；

可见测试数据

输入数据 1

2
2 2
OX
OX
3 3
XOX
OXO
XOX

输出数据 1

1
2

输入数据 2

1
1 1
O

输出数据 2

0

输入数据 3

1
1 1
X

输出数据 3

0