C. Палиндромные пути
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана матрица из $$$n$$$ строк (пронумерованных от $$$1$$$ до $$$n$$$) и $$$m$$$ столбцов (пронумерованных от $$$1$$$ до $$$m$$$). Обозначим за $$$a_{i, j}$$$ число в клетке на пересечении $$$i$$$-й строки и $$$j$$$-го столбца, каждое число либо $$$0$$$, либо $$$1$$$.

Изначально в ячейке $$$(1, 1)$$$ находится фишка, которая будет перемещена в ячейку $$$(n, m)$$$ при помощи последовательности шагов. На каждом шаге фишка перемещается либо в ячейку справа от текущей, либо в ячейку снизу (если фишка сейчас в ячейке $$$(x, y)$$$, ее можно переместить либо в $$$(x + 1, y)$$$, либо в $$$(x, y + 1)$$$). Фишка не может покидать матрицу.

Рассмотрим все пути фишки из ячейки $$$(1, 1)$$$ в ячейку $$$(n, m)$$$. Назовем путь палиндромным, если число в первой ячейке пути равно числу в последней ячейке пути, число во второй ячейке равно числу в предпоследней ячейке, и так далее.

Ваша цель — заменить минимальное количество элементов матрицы так, чтобы все пути стали палиндромными.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 200$$$) — количество наборов входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 30$$$) — размеры матрицы.

Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит $$$m$$$ целых чисел $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, m}$$$ ($$$0 \le a_{i, j} \le 1$$$).

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

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

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

Итоговые матрицы в первых трех примерах:

$$$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}$$$
$$$\begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}$$$
$$$\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$$$