VegiCat ha una matrice di interi $A = (a_{ij})$ di dimensione $n \times n$. Per ogni $1 \le i, j \le n$:

• Se $i = j$, $i = 1$ oppure $j = 1$, allora $a_{ij} = -1$.
• Altrimenti, $a_{ij}$ è un intero non negativo.

Aiuta VegiCat a costruire un grafo semplice non orientato $G$ con $n$ vertici, numerati da $1$ a $n$.

Per ogni coppia di vertici distinti $i, j$ con $i > 1$ e $j > 1$, il grafo deve soddisfare la seguente condizione: dopo aver rimosso i vertici $i$ e $j$, insieme a tutti gli archi che hanno un estremo in uno dei due vertici, devono rimanere esattamente $a_{ij}$ archi.

Ogni coppia di vertici $i, j$ viene considerata separatamente. Ciò significa che per ciascuna coppia si parte da $G$ prima che qualsiasi vertice o arco sia stato rimosso.

È garantito che esiste almeno un grafo di questo tipo. Se esistono più soluzioni, stampane una qualsiasi.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 6 \cdot 10^4$), il numero di casi di test. Segue la descrizione dei casi di test.

Per ogni caso di test, la prima riga contiene un intero $n$ ($4 \le n \le 10^3$), che indica il numero di vertici nel grafo.

Successivamente, ciascuna delle seguenti $n$ righe contiene $n$ interi separati da spazi $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), che rappresentano la matrice $A$ descritta nel testo.

È garantito che la somma totale di $n^2$ su tutti i casi di test non supera $1.2 \cdot 10^6$, e che esiste almeno un grafo corrispondente alla matrice $A$.

Output

Per ogni caso di test, stampa la matrice di adiacenza del grafo che hai costruito. Stampa $n$ righe, ciascuna contenente $n$ interi separati da spazi. Ogni intero deve essere $0$ oppure $1$. L'elemento nella $i$-esima riga e $j$-esima colonna è $1$ se c'è un arco tra i vertici $i$ e $j$, e $0$ altrimenti. Se esistono più soluzioni, stampane una qualsiasi.

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

La matrice di input effettiva avrà un solo spazio tra due interi. Gli spazi aggiuntivi nell'esempio servono unicamente a migliorare la leggibilità dell'impaginazione.