Задачи очного тура личного первенства

Макси и Мини играют в следующую игру. Квадратный лист бумаги разделяется линиями на `N\ times\ N` клеток, и в каждой клетке записывается целое число от –100 до 100. Игроки ходят по очереди. Каждый игрок может либо взять себе весь оставшийся прямоугольник, либо разрезать его по вертикальной или горизонтальной линии на два прямоугольника и взять себе любую из частей. Игра заканчивается, когда игрок при очередном ходе забирает себе всю оставшуюся фигуру. По окончании игры подсчитывается сумма чисел на взятых игроками частях. Побеждает тот игрок, у которого сумма больше.

Напишите программу, которая по значениям в клетках в начале игры определит максимальный перевес первого игрока над вторым, если оба играют максимально прибыльно для себя.

В первой строке входного файла содежится число `T` (`0\ <\ T\ ≤\ 10`) – количество тестов в файле. Каждый тест состоит из набора строк. В первой строке содержится целое число `N` (`0\ <\ N\ ≤\ 10`) – размер поля, затем следует `N` строк, в каждой содержится `N` целых чисел `A_{ij}` (`-100\ ≤\ A_{ij}\ ≤\ 100`), разделенных пробелами – числа, записанные в соответствующих клетках.

Для каждого теста вывести на соответствующей строке максимальный перевес первого игрока над вторым по окончании игры, если оба играют максимально прибыльно для себя.

2
3
1 1 1
1 1 1
1 1 1
2
-10 1
1 1

9
-7