以下题面由 AI 翻译。

问题描述

给定一个包含$n$行和$m$列的表格。最初，第$i$行第$j$列的单元格具有颜色$a_{i,j}$。

如果两个单元格不共享一条边，则它们被称为陌生人。陌生人可以通过角接触彼此。

如果一个单元格集合中的所有单元格都是陌生人，则称该集合为陌生人集合。仅包含一个或零个单元格的集合默认是陌生人集合。

在一步操作中，你可以选择任意一组陌生人，且这些单元格具有相同的颜色，并将它们涂成另一种颜色。你可以选择最终的颜色。

要使整个表格变为同一种颜色，需要进行的最少步骤数是多少？

输入格式

• 第一行包含一个整数$t$（$1 \le t \le 10^4$）——测试用例的数量。
• 接下来是$t$个测试用例。

每个测试用例的第一行包含两个整数$n$和$m$（$1 \le n \le m \le 700$）——表格的行数和列数。

接下来的$n$行包含对应行中各单元格的颜色$a_{i, 1}, \dots, a_{i, m}$（$1 \le a_{i, j} \le nm$）。

保证所有测试用例的总$nm$不超过$5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数——使整个表格变为同一种颜色所需的最少步骤数。

示例

输入

输入1|2,3,8,9
4
1 1
1
3 3
1 2 1
2 3 2
1 3 1
1 6
5 4 5 4 4 5
3 4
1 4 2 2
1 4 3 5
6 6 3 5

输出

0
2
1
10

注意

在第一个测试用例中，表格已经全部是同一种颜色。

在第二个测试用例中，你可以选择所有颜色为$1$的单元格并将其涂成颜色$3$。然后选择所有颜色为$2$的单元格并将其也涂成颜色$3$。

在第三个测试用例中，你可以选择所有颜色为$5$的单元格并将其涂成颜色$4$。