E. Xpinxor Grix
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана матрица $$$a$$$ размера $$$n \times m$$$, каждая ячейка которой содержит неотрицательное целое число. Число, находящееся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца матрицы, называется $$$a_{i,j}$$$.

Определим $$$f(i)$$$ и $$$g(j)$$$ как XOR всех чисел в $$$i$$$-й строке и $$$j$$$-м столбце соответственно. За одну операцию вы можете либо:

  • Выбрать любую строку $$$i$$$, затем присвоить $$$a_{i,j} := g(j)$$$ для каждого $$$1 \le j \le m$$$; либо
  • Выбрать любой столбец $$$j$$$, затем присвоить $$$a_{i,j} := f(i)$$$ для каждого $$$1 \le i \le n$$$.
Пример применения операции к столбцу $$$2$$$ матрицы.

В этом примере, когда мы применяем операцию к столбцу $$$2$$$, все элементы в этом столбце изменяются следующим образом:

  • $$$a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0$$$
  • $$$a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3$$$
  • $$$a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1$$$
  • $$$a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29$$$

Вы можете применять операции любое количество раз. Затем мы вычислим $$$\textit{красоту}$$$ финальной матрицы, суммируя абсолютные разности между всеми парами её соседних ячеек.

Более формально, $$$\textit{красота}(a) = \sum|a_{x,y} - a_{r,c}|$$$ для всех ячеек $$$(x, y)$$$ и $$$(r, c)$$$, если они соседние. Две ячейки считаются соседними, если они имеют общую сторону.

Найдите минимальную $$$\textit{красоту}$$$ среди всех достижимых матриц.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 250$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 15$$$) — количество строк и столбцов матрицы $$$a$$$ соответственно.

Далее идут $$$n$$$ строк, каждая из которых содержит $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$0 \le a_{i,j} < 2^{20}$$$) — описание матрицы $$$a$$$.

Гарантируется, что сумма $$$(n^2 + m^2)$$$ по всем наборам входных данных не превышает $$$500$$$.

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

Для каждого набора входных данных выведите одно целое число $$$b$$$ — наименьшая возможная $$$\textit{красота}$$$ матрицы.

Пример
Входные данные
4
1 2
1 3
2 3
0 1 0
5 4 4
2 3
0 2 4
4 5 1
3 3
1 2 3
4 5 6
7 8 9
Выходные данные
1
3
13
24
Примечание

Обозначим $$$r(i)$$$ как операцию первого типа, примененную к $$$i$$$-й строке, и $$$c(j)$$$ как операцию второго типа, примененную к $$$j$$$-му столбцу.

В первом наборе входных данных вы можете применить операцию $$$c(1)$$$, которая присвоит $$$a_{1,1} := 1 \oplus 3 = 2$$$. Затем мы получим эту матрицу:

23

Во втором наборе входных данных вы можете применить операцию $$$r(1)$$$, которая присвоит:

  • $$$a_{1,1} := g(1) = 0 \oplus 5 = 5$$$
  • $$$a_{1,2} := g(2) = 1 \oplus 4 = 5$$$
  • $$$a_{1,3} := g(3) = 0 \oplus 4 = 4$$$

Финальная матрица после выполнения операции:

554
544

В третьем наборе входных данных лучший способ достичь минимальной $$$\textit{красота}$$$ — применить три операции: $$$c(3)$$$, $$$r(2)$$$ и $$$c(2)$$$. Финальная матрица:

046
456