题目描述

给定一个包含 $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

输入 #1

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

输出 #1

0
2
1
10

说明/提示

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

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

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