VegiCat has an $n \times n$ integer matrix $A = (a_{ij})$. For each $1 \le i, j \le n$:

• If $i = j$, $i = 1$, or $j = 1$, then $a_{ij} = -1$.
• Otherwise, $a_{ij}$ is a nonnegative integer.

Help VegiCat construct an undirected simple graph $G$ with $n$ vertices, numbered from $1$ to $n$.

For every pair of distinct vertices $i, j$ with $i > 1$ and $j > 1$, the graph must satisfy the following condition: after deleting vertices $i$ and $j$, together with all edges that have an endpoint at either vertex, exactly $a_{ij}$ edges must remain.

Each pair of vertices $i, j$ is considered separately. That is, for each pair, start with $G$ before any vertices or edges have been deleted.

It is guaranteed that at least one such graph exists. If there are multiple solutions, output any of them.

Input

The first line contains an integer $T$ ($1 \le T \le 6 \cdot 10^4$), the number of test cases. The description of the test cases follows.

For each test case, the first line contains an integer $n$ ($4 \le n \le 10^3$), denoting the number of vertices in the graph.

Then each of the next $n$ lines contains $n$ space-separated integers $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), representing the matrix $A$ described in the statement.

It is guaranteed that the total sum of $n^2$ over all test cases does not exceed $1.2 \cdot 10^6$, and that at least one graph corresponding to matrix $A$ exists.

Output

For each test case, output the adjacency matrix of the graph you construct. Output $n$ lines, each containing $n$ space-separated integers. Each integer must be either $0$ or $1$. The entry in the $i$-th row and $j$-th column is $1$ if there is an edge between vertices $i$ and $j$, and $0$ otherwise. If there are multiple solutions, output any of them.

Examples

Input 1

2
5
-1 -1 -1 -1 -1
-1 -1  3  1  2
-1  3 -1  2  2
-1  1  2 -1  1
-1  2  2  1 -1
7
-1 -1 -1 -1 -1 -1 -1
-1 -1  4  5  3  6  5
-1  4 -1  5  4  5  5
-1  5  5 -1  5  7  5
-1  3  4  5 -1  4  4
-1  6  5  7  4 -1  5
-1  5  5  5  4  5 -1

Output 1

0 1 0 1 1
1 0 0 0 0
0 0 0 1 0
1 0 1 0 1
1 0 0 1 0
0 1 1 0 1 0 0
1 0 0 0 0 1 1
1 0 0 0 1 0 1
0 0 0 0 1 1 0
1 0 1 1 0 0 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0

Note

The actual input matrix will only have a single space between two integers. The extra spaces in the sample are designed to enhance the readability of the layout.