VegiCatilla on $n \times n$ -kokoinen kokonaislukumatriisi $A = (a_{ij})$. Jokaiselle $1 \le i, j \le n$:
- Jos $i = j$, $i = 1$ tai $j = 1$, niin $a_{ij} = -1$.
- Muussa tapauksessa $a_{ij}$ on epänegatiivinen kokonaisluku.
Auta VegiCatia muodostamaan suuntaamaton yksinkertainen verkko $G$, jossa on $n$ solmua numeroituina $1$:stä $n$:ään.
Jokaiselle erillisten solmujen parille $i, j$, joille $i > 1$ ja $j > 1$, verkon on täytettävä seuraava ehto: kun solmut $i$ ja $j$ sekä kaikki kaaret, joiden toinen päätepiste on jompikumpi näistä solmuista, poistetaan, jäljelle on jäätävä täsmälleen $a_{ij}$ kaarta.
Jokaista solmuparia $i, j$ tarkastellaan erikseen. Toisin sanoen jokaisen parin kohdalla lähdetään verkosta $G$ ennen kuin yhtäkään solmua tai kaarta on poistettu.
On taattu, että vähintään yksi tällainen verkko on olemassa. Jos ratkaisuja on useita, tulosta mikä tahansa niistä.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 6 \cdot 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.
Jokaisen testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($4 \le n \le 10^3$), joka ilmaisee verkon solmujen lukumäärän.
Tämän jälkeen kukin seuraavista $n$ rivistä sisältää $n$ välilyönnein erotettua kokonaislukua $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), jotka esittävät tehtävänannossa kuvattua matriisia $A$.
On taattu, että lukujen $n^2$ kokonaissumma yli kaikkien testitapausten ei ylitä arvoa $1.2 \cdot 10^6$, ja että matriisia $A$ vastaavia verkkoja on olemassa vähintään yksi.
Tuloste
Tulosta jokaiselle testitapaukselle muodostamasi verkon vierusmatriisi. Tulosta $n$ riviä, joista jokainen sisältää $n$ välilyönnein erotettua kokonaislukua. Jokaisen kokonaisluvun on oltava joko $0$ tai $1$. Rivin $i$ ja sarakkeen $j$ alkio on $1$, jos solmujen $i$ ja $j$ välillä on kaari, ja muuten $0$. Jos ratkaisuja on useita, tulosta mikä tahansa niistä.
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
Todellisessa syötematriisissa kahden kokonaisluvun välissä on vain yksi välilyönti. Esimerkin ylimääräiset välilyönnit on tarkoitettu parantamaan asetelman luettavuutta.