VegiCat á $n \times n$ heiltölufylki $A = (a_{ij})$. Fyrir hvert $1 \le i, j \le n$:

• Ef $i = j$, $i = 1$ eða $j = 1$, þá er $a_{ij} = -1$.
• Annars er $a_{ij}$ óneikvæð heiltala.

Hjálpaðu VegiCat að smíða óstefnt einfalt net $G$ með $n$ hnútum, númeruðum frá $1$ til $n$.

Fyrir hvert par ólíkra hnúta $i, j$ þar sem $i > 1$ og $j > 1$ verður netið að uppfylla eftirfarandi skilyrði: eftir að hnútunum $i$ og $j$ hefur verið eytt, ásamt öllum leggjum sem hafa endapunkt í öðrum hvorum hnútnum, verða nákvæmlega $a_{ij}$ leggir að vera eftir.

Hvert par hnúta $i, j$ er skoðað í sitt hvoru lagi. Það er, fyrir hvert par er byrjað með $G$ áður en nokkrum hnútum eða leggjum hefur verið eytt.

Tryggt er að að minnsta kosti eitt slíkt net sé til. Ef fleiri en ein lausn eru til skal prenta hvaða lausn sem er.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 6 \cdot 10^4$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Fyrir hvert prófunartilfelli inniheldur fyrsta línan heiltölu $n$ ($4 \le n \le 10^3$), sem táknar fjölda hnúta í netinu.

Síðan inniheldur hver af næstu $n$ línum $n$ heiltölur aðskildar með bili $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), sem tákna fylkið $A$ sem lýst er í dæminu.

Tryggt er að heildarsumma $n^2$ yfir öll prófunartilfelli fari ekki yfir $1.2 \cdot 10^6$, og að að minnsta kosti eitt net sem samsvarar fylkinu $A$ sé til.

Úttak

Fyrir hvert prófunartilfelli skal prenta grannafylki netsins sem þú smíðar. Prentaðu $n$ línur, þar sem hver lína inniheldur $n$ heiltölur aðskildar með bili. Hver heiltala verður að vera annaðhvort $0$ eða $1$. Stakið í $i$-tu röð og $j$-ta dálki er $1$ ef leggur liggur á milli hnúta $i$ og $j$, en $0$ annars. Ef fleiri en ein lausn eru til skal prenta hvaða lausn sem er.

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

Hið raunverulega inntaksfylki mun aðeins hafa eitt bil á milli tveggja heiltalna. Aukabilin í sýnidæminu eru ætluð til að auka læsileika uppsetningarinnar.