Grid Xor

题意翻译

给定 $n \times n$ 的矩阵 $a$，求满足 $a$ 中任意一个元素等于 $b$ 中与其相邻元素的异或和的矩阵 $b$ 的异或和。 $2 \le n \le 1000$，$n$ 是偶数。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 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.

输入输出样例

输入样例 #1

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

输出样例 #1

4
9
5

说明

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 $