B. Множества незнакомцев
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана таблица из $$$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$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — наименьшее количество шагов, чтобы покрасить все ячейки таблицы в один цвет.

Пример
Входные данные
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$$$.