VegiCat har en heltallsmatrise $A = (a_{ij})$ av størrelse $n \times n$. For hver $1 \le i, j \le n$:

• Hvis $i = j$, $i = 1$ eller $j = 1$, så er $a_{ij} = -1$.
• Ellers er $a_{ij}$ et ikke-negativt heltall.

Hjelp VegiCat med å konstruere en urettet enkel graf $G$ med $n$ noder, nummerert fra $1$ til $n$.

For hvert par av ulike noder $i, j$ med $i > 1$ og $j > 1$, må grafen oppfylle følgende betingelse: etter å ha slettet nodene $i$ og $j$, sammen med alle kanter som har et endepunkt i en av disse nodene, må det være nøyaktig $a_{ij}$ kanter igjen.

Hvert par av noder $i, j$ betraktes separat. Det vil si at for hvert par starter man med $G$ før noen noder eller kanter er slettet.

Det er garantert at minst én slik graf eksisterer. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 6 \cdot 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($4 \le n \le 10^3$), som angir antallet noder i grafen.

Deretter inneholder hver av de neste $n$ linjene $n$ mellomromseparerte heltall $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), som representerer matrisen $A$ beskrevet i oppgaveteksten.

Det er garantert at den totale summen av $n^2$ over alle testtilfeller ikke overstiger $1.2 \cdot 10^6$, og at det finnes minst én graf som tilsvarer matrisen $A$.

Utdata

For hvert testtilfelle skal du skrive ut nabomatrisen til grafen du konstruerer. Skriv ut $n$ linjer, der hver linje inneholder $n$ mellomromseparerte heltall. Hvert heltall må være enten $0$ eller $1$. Verdien i rad $i$ og kolonne $j$ er $1$ hvis det er en kant mellom nodene $i$ og $j$, og $0$ ellers. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.

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

Den faktiske inndatamatrisen vil kun ha ett enkelt mellomrom mellom to heltall. De ekstra mellomrommene i eksempelet er lagt inn for å gjøre oppsettet lettere å lese.