codeforces#P1628C. Grid Xor

    ID: 32666 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsgreedyimplementationinteractivemath

Grid Xor

Description

Note: The XOR-sum of set $\{s_1,s_2,\ldots,s_m\}$ is defined as $s_1 \oplus s_2 \oplus \ldots \oplus s_m$, where $\oplus$ denotes the bitwise XOR operation.

After almost winning IOI, Victor bought himself an $n\times n$ grid containing integers in each cell. $n$ is an even integer. The integer in the cell in the $i$-th row and $j$-th column is $a_{i,j}$.

Sadly, Mihai stole the grid from Victor and told him he would return it with only one condition: Victor has to tell Mihai the XOR-sum of all the integers in the whole grid.

Victor doesn't remember all the elements of the grid, but he remembers some information about it: For each cell, Victor remembers the XOR-sum of all its neighboring cells.

Two cells are considered neighbors if they share an edge — in other words, for some integers $1 \le i, j, k, l \le n$, the cell in the $i$-th row and $j$-th column is a neighbor of the cell in the $k$-th row and $l$-th column if $|i - k| = 1$ and $j = l$, or if $i = k$ and $|j - l| = 1$.

To get his grid back, Victor is asking you for your help. Can you use the information Victor remembers to find the XOR-sum of the whole grid?

It can be proven that the answer is unique.

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single even integer $n$ ($2 \leq n \leq 1000$) — the size of the grid.

Then follows $n$ lines, each containing $n$ integers. The $j$-th integer in the $i$-th of these lines represents the XOR-sum of the integers in all the neighbors of the cell in the $i$-th row and $j$-th column.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $1000$ and in the original grid $0 \leq a_{i, j} \leq 2^{30} - 1$.

Hack Format

To hack a solution, use the following format:

The first line should contain a single integer t ($1 \le t \le 100$) — the number of test cases.

The first line of each test case should contain a single even integer $n$ ($2 \leq n \leq 1000$) — the size of the grid.

Then $n$ lines should follow, each containing $n$ integers. The $j$-th integer in the $i$-th of these lines is $a_{i,j}$ in Victor's original grid. The values in the grid should be integers in the range $[0, 2^{30}-1]$

The sum of $n$ over all test cases must not exceed $1000$.

For each test case, output a single integer — the XOR-sum of the whole grid.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single even integer $n$ ($2 \leq n \leq 1000$) — the size of the grid.

Then follows $n$ lines, each containing $n$ integers. The $j$-th integer in the $i$-th of these lines represents the XOR-sum of the integers in all the neighbors of the cell in the $i$-th row and $j$-th column.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $1000$ and in the original grid $0 \leq a_{i, j} \leq 2^{30} - 1$.

Hack Format

To hack a solution, use the following format:

The first line should contain a single integer t ($1 \le t \le 100$) — the number of test cases.

The first line of each test case should contain a single even integer $n$ ($2 \leq n \leq 1000$) — the size of the grid.

Then $n$ lines should follow, each containing $n$ integers. The $j$-th integer in the $i$-th of these lines is $a_{i,j}$ in Victor's original grid. The values in the grid should be integers in the range $[0, 2^{30}-1]$

The sum of $n$ over all test cases must not exceed $1000$.

Output

For each test case, output a single integer — the XOR-sum of the whole grid.

Samples

3
2
1 5
5 1
4
1 14 8 9
3 1 5 9
4 13 11 1
1 15 4 11
4
2 4 1 6
3 7 3 10
15 9 4 2
12 7 15 1
4
9
5

Note

For the first test case, one possibility for Victor's original grid is:

$1$$3$
$2$$4$

For the second test case, one possibility for Victor's original grid is:

$3$$8$$8$$5$
$9$$5$$5$$1$
$5$$5$$9$$9$
$8$$4$$2$$9$

For the third test case, one possibility for Victor's original grid is:

$4$$3$$2$$1$
$1$$2$$3$$4$
$5$$6$$7$$8$
$8$$9$$9$$1$