将为您提供一个包含 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 将表格的所有单元格绘制为相同颜色的最小步骤数。
示例
输入复制
41 113 31 2 12 3 21 3 11 65 4 5 4 4 53 41 4 2 21 4 3 56 6 3 5
输出复制
0 2 1 10
注意
在第一个测试用例中,表格从一开始就用一种颜色绘制。
在第二个测试用例中,例如,您可以选择颜色为 $$$1$$$ 的所有单元格并将它们绘制为 $$$3$$$。然后选择颜色为 $$$2$$$ 的所有单元格,并将它们绘制为 $$$3$$$。
在第三个测试用例中,您可以选择颜色为 $$$5$$$ 的所有单元格并将它们绘制为颜色 $$$4$$$。