J. MEX Should Be Same
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

有一个 $$$n\times n$$$ 的二维数组，其中每个数都是 $$$0$$$ 到 $$$n$$$ 的整数，请你至多修改数组中的 $$$\lfloor \frac{n\times n}{2}\rfloor$$$ 个数，将其改为另一个 $$$0$$$ 到 $$$n$$$ 的整数。所有修改操作完成后，使得数组每一行、每一列的所有数字的 MEX 值都等于一个相同的数字。

MEX 是指所有数字中最小的未出现的非负整数，例如 $$$MEX(\{1,2,3\})=0$$$、$$$MEX(\{1,0,5,7,4,1\})=2$$$ 和 $$$MEX(\{0,0,1,1,1,3\})=2$$$。

$$$\lfloor x\rfloor$$$ 代表对于 $$$x$$$ 向下取整，例如 $$$\lfloor \frac{1}{2} \rfloor=0$$$ 、 $$$\lfloor \frac{9}{2} \rfloor=4$$$ 和 $$$\lfloor \frac{16}{2} \rfloor=8$$$。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，一个整数 $$$n(1\le n\le 1000)$$$，代表二维数组的大小。

接下来的 $$$n$$$ 行，每行 $$$n$$$ 个数字，第 $$$i$$$ 行第 $$$j$$$ 列的数字 $$$a_{i,j}(0\le a_{i,j}\le n)$$$ 代表数组中第 $$$i$$$ 行第 $$$j$$$ 列的数字。

保证同一测试点内的 $$$n^2$$$ 的总和不超过 $$$10^6$$$。

Output

对于每组数据，输出一个 $$$n\times n$$$ 的矩阵，代表修改后的矩阵，矩阵每行每列的 MEX 值需要相同。

可以被证明的是，在题目要求的条件下，一定存在一种修改数组的方案，满足题目的要求。

Example
Input
4
1
1
3
0 1 2
1 2 0
2 1 3
4
1 2 0 2
4 0 4 0
0 1 0 0
3 0 4 1
2
2 2
0 2
Output
1
0 1 2
1 2 0
2 0 1
1 2 0 2
2 0 1 0 
0 1 0 2
2 0 2 1
2 2
1 2