VegiCat har en heltalsmatris $A = (a_{ij})$ av storlek $n \times n$. För varje $1 \le i, j \le n$:
- Om $i = j$, $i = 1$ eller $j = 1$, så är $a_{ij} = -1$.
- Annars är $a_{ij}$ ett icke-negativt heltal.
Hjälp VegiCat att konstruera en oriktad enkel graf $G$ med $n$ hörn, numrerade från $1$ till $n$.
För varje par av skilda hörn $i, j$ med $i > 1$ och $j > 1$ måste grafen uppfylla följande villkor: efter att hörnen $i$ och $j$ har tagits bort, tillsammans med alla kanter som har en ändpunkt i något av dessa hörn, måste exakt $a_{ij}$ kanter återstå.
Varje par av hörn $i, j$ betraktas separat. Det vill säga, för varje par utgår man från $G$ innan några hörn eller kanter har tagits bort.
Det garanteras att minst en sådan graf existerar. Om det finns flera lösningar, skriv ut vilken som helst av dem.
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 6 \cdot 10^4$), antalet testfall. Beskrivningen av testfallen följer.
För varje testfall innehåller den första raden ett heltal $n$ ($4 \le n \le 10^3$), som anger antalet hörn i grafen.
Därefter innehåller var och en av de följande $n$ raderna $n$ blankstegsavgränsade heltal $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), vilka representerar matrisen $A$ som beskrivs i uppgiften.
Det garanteras att den totala summan av $n^2$ över alla testfall inte överstiger $1.2 \cdot 10^6$, och att det finns minst en graf som motsvarar matrisen $A$.
Utdata
För varje testfall, skriv ut grannmatrisen för grafen du konstruerar. Skriv ut $n$ rader som var och en innehåller $n$ blankstegsavgränsade heltal. Varje heltal måste vara antingen $0$ eller $1$. Värdet på rad $i$ och kolumn $j$ är $1$ om det finns en kant mellan hörnen $i$ och $j$, och $0$ annars. Om det finns flera lösningar, skriv ut vilken 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 faktiska indatamatrisen har endast ett enda blanksteg mellan två heltal. De extra blankstegen i exemplet är till för att göra layouten mer lättläst.