There are (n \times m) crossroads in the city, named crossroad ((1, 1), (1, 2),\ldots, (n, m)). The first number represents the row, and the second represents the column. There exists and only exists streets between ((i,j)) and ((i+1,j)) or between ((i,j)) and ((i,j+1)). The street between ((i, j)) and ((i + 1, j)) has a weight of (w_{i,j}), and the street between ((i, j)) and ((i, j + 1)) has a weight of (v_{i,j}). Simons wants some streets reconstructed. Due to some accidents, some of the streets cannot be reconstructed, while others are optional to be reconstructed. For each crossroad, if the number of reconstructed streets adjacent to it is even , Simons calls the crossroad elegant . If all the crossroads are elegant , Simons calls the reconstruction nice . The beauty of a reconstruction is calculated as follows: At first, the beauty is (0). For each row (i) from (1) to (n - 1), let the columns of the streets reconstructed be (c_1 \lt c_2 \lt c_3 \lt \cdots), add (w_{i, c_1} - w_{i, c_2} + w_{i, c_3} - w_{i, c_4}+\cdots) to the beauty . Similarly, for each column (j) from (1) to (m - 1), let the rows of the streets reconstructed be (r_1 \lt r_2 \lt r_3 \lt \cdots), add (v_{r_1, j} - v_{r_2, j} + v_{r_3, j} - v_{r_4, j}+\cdots) to the beauty . In other words, if a street is an odd-indexed one reconstructed in its row or column, add its weight to the beauty ; else subtract it from the beauty . For example, consider the streets and crossroads below without any streets that cannot be reconstructed: We can have a nice reconstruction as follows: The beauty of the reconstruction is (3+4+2-(-9)-(-2)+9+1-(-1)-(-3)-(-4)=38). Help Simons find the maximum beauty among all the nice reconstructions. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 5\cdot 10^4)). The description of the test cases follows. Th