D. Hillington
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yalikesi just took a trip to Hillington, a city so hilly that you're either walking uphill or downhill, with no in-between! Being an avid land surveying fan, Yalikesi brought his equipment to create an elevation map of the city, but limited time meant he was only able to calculate the elevation at a few locations.

Hillington can be represented by a $$$n$$$-by-$$$n$$$ grid. The tile in the $$$i$$$-th row and $$$j$$$-th column of the grid has an integer height, denoted $$$h_{i,j}$$$. For each cell, Yalikesi either knows the exact value of its height, or has not measured it yet.

A valid completion of Yalikesi's observations is a $$$n$$$-by-$$$n$$$ grid, denoted $$$a$$$, satisfying both the following:

  • The heights of any two adjacent cells in $$$a$$$ differs by exactly $$$1$$$.
  • For all $$$h_{i,j}$$$ which have been measured, $$$a_{i,j} = h_{i,j}$$$.

Note that $$$a_{i,j}$$$ does not necessarily have to be positive.

A cell $$$(i,j)$$$ is said to be uniquely determined if the integer in it is the same across all valid completions.

You need to find all uniquely determined cells in $$$h$$$, and report the integers in them.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).

The first line of each test contains $$$n$$$, the size of the grid ($$$1 \le n \le 500$$$).

The next $$$n$$$ lines contain $$$n$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line, which we denote $$$b_{i,j}$$$, represents the value of $$$h_{i,j}$$$.

  • If the height of cell $$$(i,j)$$$ is unknown, then $$$b_{i,j} = 0$$$.
  • Otherwise, $$$b_{i,j}$$$ will be a positive integer, the height of that cell ($$$1 \le b_{i,j} \le 10^9$$$).

Note that $$$h_{i,j}$$$ for unmeasured cells do not have to be positive, and may be greater than $$$10^9$$$.

It is guaranteed the sum of $$$n^2$$$ over all tests does not exceed $$$250\,000$$$.

It is guaranteed that at least one valid completion exists, and that the height of at least one cell is known.

Output

For each test, output $$$n$$$ lines containing $$$n$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line represents the cell $$$(i,j)$$$. If it is uniquely determined, output its height. Otherwise, output 0.

We can show that under the constraints of the problem, any uniquely determined cell will have a nonzero value.

Note that in the sample tests, a newline is printed between test cases. This is only for ease of reading, and you do not need it in your solution.

Example
Input
5
5
0 0 0 0 0
0 0 0 6 0
0 0 0 0 0
3 0 0 0 0
0 1 0 0 0
1
999
3
2 1 2
1 0 1
2 1 2
6
0 8 9 8 7 8
8 7 8 9 8 7
9 8 0 8 0 8
8 7 6 7 8 9
0 6 7 8 9 0
0 7 6 7 8 0
2
999999999 1000000000
1000000000 0
Output
0 0 0 0 0
0 4 5 6 0
0 3 4 5 0
3 2 3 4 0
2 1 2 3 0

999

2 1 2
1 0 1
2 1 2

0 8 9 8 7 8
8 7 8 9 8 7
9 8 7 8 0 8
8 7 6 7 8 9
7 6 7 8 9 0
0 7 6 7 8 0

999999999 1000000000
1000000000 0
Note

In the first test, here are two possible valid completions of the grid:

Note that the cells in red are all different between the two grids, therefore they cannot be uniquely determined.

In this case, it also happens that the rest of the cells are the same across all valid completions, so they are uniquely determined.

In the second case, note that the grid may already have all heights measured.

In the third case, the square in the center can be either $$$0$$$ or $$$2$$$. $$$a_{i,j}$$$ does not necessarily have to be positive, so this square is not uniquely determined.