G. The Matrix
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are Neo, a programmer who has discovered that the world we live in is nothing but a two-dimensional Matrix. With the help of some friends, you have escaped the Matrix. But your friends are still trapped inside. The Agents have assigned a danger level to the Matrix, and you must minimize it to save your friends.

The Matrix has $$$n$$$ rows and $$$m$$$ columns, where each element is a non-negative integer that can be represented by $$$30$$$ bits. The danger level of a row is defined as the bitwise XOR of all numbers in that row, and the danger level of a column as the bitwise XOR of all numbers in that column. The total danger level of the Matrix is the sum of the danger levels of all rows and all columns in the Matrix.

Formally, let's define the element in the $$$i$$$-th row and $$$j$$$-th column $$$(1 \le i \le n, 1 \le j \le m)$$$ of the Matrix as $$$M_{i,j}$$$. The danger level of the $$$i$$$-th row, $$$r_i = M_{i,1} \oplus M_{i,2} \oplus \dots \oplus M_{i,m}$$$. The danger level of the $$$j$$$-th column, $$$c_j = M_{1,j} \oplus M_{2,j} \oplus \dots \oplus M_{n,j}$$$. The total danger level of the Matrix $$$= (r_1 + r_2 + \dots + r_n) + (c_1 + c_2 + \dots + c_m)$$$.

With your newfound abilities, you can alter at most one element of the Matrix, replacing it with any non-negative integer to reduce the danger level.

Find the minimum total danger level achievable.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 5 \times 10^5)$$$ — the number of rows and columns in the Matrix.

The next $$$n$$$ lines each contains $$$m$$$ space-separated integers $$$(0 \le M_{i,j} \lt 2^{30})$$$ — the elements of the Matrix. The $$$j$$$-th integer in the $$$i$$$-th of these lines denotes $$$M_{i,j}$$$.

It is guaranteed that the sum of $$$n \times m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer in a line — the minimum total danger level achievable.

Example
Input
4
2 3
13 9 24
11 20 27
3 3
5 5 5
5 5 5
5 5 5
1 4
1 2 3 4
4 3
0 0 0
0 0 0
0 0 0
0 0 0
Output
14
20
6
0
Note

In the first test case, the danger level of the first row is $$$28$$$ and the danger level of the second row is $$$4$$$. The danger levels of the columns are $$$6$$$, $$$29$$$, and $$$3$$$ respectively. This makes the total danger level $$$70$$$. By replacing $$$9$$$ with $$$21$$$, the danger level can be brought down to $$$14$$$. It can be proven that this is the minimum total danger level that can be achieved.