Story

You, a genius hacker, have hacked an enemy robot and obtained secret image data.
However, you noticed that the image data had been subjected to a light two-dimensional convolution, and that the order of its pixels was randomly shuffled when it passed through security.
It has become difficult to uniquely restore the original image data, but constructing an example of what the original image could have been may still reveal something.
Write a program that constructs one example of the original image data.

Problem Statement

There is an $N \times N$ matrix $A$. Each element of the matrix $A$ is known to be a non-negative integer.

Now, define an $(N-1) \times (N-1)$ matrix $B$ as follows. $$ B_{i,j} = A_{i, j} + A_{i, j+1} + A_{i+1, j} + A_{i+1, j+1} $$ You are given an array $C$ obtained by arranging the $(N-1)^2$ elements of $B$ in random order. Find one example of a matrix that could be $A$.
If no such matrix exists, report that fact.

$T$ test cases are given; solve each of them.

Constraints

• All input values are integers
• $1 \leq T \leq 10^4$
• $2 \leq N \leq 700$
• $0 \leq C_i \leq 10^6 - 1$
• The sum of $N^2$ in $1$ input file does not exceed $5 \times 10^5$

Input

The input is given from standard input in the following format. Here, $case_i$ denotes the $i$-th case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N$
$C_1\ C_2\ \cdots\ C_{(N-1)^2}$

Output

For each case, output -1 if no matrix that could be $A$ exists; otherwise, output one example of such a matrix in the following format.

$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \cdots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$

Print a newline at the end of the output for each case.

Sample

3
3
2 0 2 5
2
9
4
3 1 4 1 5 9 2 6 5

2 0 1
0 0 1
0 0 4
2 0
2 5
1 1 0 0
1 0 0 1
2 2 0 4
1 4 0 0