B. Коробка с числами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана прямоугольная сетка с $$$n$$$ строками и $$$m$$$ столбцами. В ячейке, расположенной на $$$i$$$-й строке сверху и $$$j$$$-м столбце слева, записано значение $$$a_{ij}$$$.

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выберите любые две соседние ячейки и умножьте значения в них на $$$-1$$$. Две ячейки называются соседними, если они имеют общую сторону.

Обратите внимание, что одну и ту же ячейку можно использовать несколько раз при различных операциях.

Вас интересует $$$X$$$, сумма всех чисел в сетке.

Какое максимально возможное $$$X$$$ вы можете получить с помощью данных операций?

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

Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Описание наборов входных данных приведено ниже.

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

Каждая из следующих $$$n$$$ строк содержит по $$$m$$$ целых чисел, $$$j$$$-й элемент в $$$i$$$-й строке  — $$$a_{ij}$$$ ($$$-100\leq a_{ij}\le 100$$$).

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

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

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

В первом наборе входных данных всегда будет как минимум одна $$$-1$$$, так что ответ равен $$$2$$$.

Во втором наборе входных данных можно шесть раз использовать операцию для элементов, соседних по горизонтали, и сделать все числа неотрицательными. Так что ответ: $$$2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$$$.