VegiCat tiene una matriz de enteros $A = (a_{ij})$ de tamaño $n \times n$. Para cada $1 \le i, j \le n$:

• Si $i = j$, $i = 1$ o $j = 1$, entonces $a_{ij} = -1$.
• En caso contrario, $a_{ij}$ es un entero no negativo.

Ayuda a VegiCat a construir un grafo simple no dirigido $G$ con $n$ vértices, numerados de $1$ a $n$.

Para cada par de vértices distintos $i, j$ con $i > 1$ y $j > 1$, el grafo debe satisfacer la siguiente condición: después de eliminar los vértices $i$ y $j$, junto con todas las aristas que tengan un extremo en cualquiera de los dos vértices, deben quedar exactamente $a_{ij}$ aristas.

Cada par de vértices $i, j$ se considera por separado. Es decir, para cada par se comienza con $G$ antes de que se haya eliminado cualquier vértice o arista.

Se garantiza que existe al menos un grafo de este tipo. Si hay múltiples soluciones, imprime cualquiera de ellas.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 6 \cdot 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($4 \le n \le 10^3$), que denota el número de vértices en el grafo.

Luego, cada una de las siguientes $n$ líneas contiene $n$ enteros separados por espacios $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), que representan la matriz $A$ descrita en el enunciado.

Se garantiza que la suma total de $n^2$ en todos los casos de prueba no supera $1.2 \cdot 10^6$, y que existe al menos un grafo correspondiente a la matriz $A$.

Salida

Para cada caso de prueba, imprime la matriz de adyacencia del grafo que construyas. Imprime $n$ líneas, cada una con $n$ enteros separados por espacios. Cada entero debe ser $0$ o $1$. La entrada en la $i$-ésima fila y la $j$-ésima columna es $1$ si hay una arista entre los vértices $i$ y $j$, y $0$ en caso contrario. Si hay múltiples soluciones, imprime cualquiera de ellas.

Ejemplos

Entrada 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

Salida 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

Nota

La matriz de entrada real solo tendrá un único espacio entre dos enteros. Los espacios adicionales en el ejemplo están diseñados para mejorar la legibilidad de la presentación.