Вам задана матрица из $$$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
Итоговые матрицы в первых трех примерах:
