该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个 n×m 的整数矩阵，其中第 i 行第 j 列的元素为 aij。 你可以进行任意多次如下操作： 选择矩阵中的两个相邻元素，将它们均乘以 −1。 同一个元素可以被选中多次。 你需要通过上述操作，使得矩阵中所有元素的和尽可能大。 计算并输出这个和的最大可能值。 1≤T≤100, 2≤n,m≤10, −100≤aij≤100

Input

第一行包含整数 T，表示共有 T 组测试数据。 每组数据第一行包含两个整数 n,m。 接下来 n 行，每行包含 m 个整数，表示整个矩阵，其中第 i 行第 j 列的数为 aij。

Output

每组数据输出一行结果，表示矩阵的所有元素的最大可能和。

Samples

2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5

2
30

Note

在第一个测试用例中，至少会有一个 −1，因此答案是 2。

在第二个测试用例中，我们可以使用操作六次，将相邻的水平元素都变为非负数。因此答案是：2×1+3×2+3×3+2×4+1×5=30。