CF2069B Set of Strangers

给定一个包含 $n$ 行 $m$ 列的表格。初始时，第 $i$ 行第 $j$ 列的单元格颜色为 $a_{i, j}$。 我们称两个单元格是陌生人（strangers）如果它们不共享任何一条边（允许通过角落接触）。 我们称一个单元格集合为陌生人集合（set of strangers），当且仅当集合中任意两个单元格都是陌生人。根据定义，包含不超过一个单元格的集合总是陌生人集合。 在每一步操作中，你可以选择一个满足以下条件的陌生人集合：集合中所有单元格颜色相同，并将它们全部涂成另一种颜色（可以选择任意一种颜色作为结果颜色）。 问：要将整个表格涂成同一种颜色，最少需要多少步操作？

第一行包含一个整数 $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$ 的单元格并将其涂成 $3$，然后选择所有颜色为 $2$ 的单元格也涂成 $3$。 在第三个测试用例中，可以选择所有颜色为 $5$ 的单元格并将其涂成 $4$。 翻译由 DeepSeek R1 完成