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.