VegiCat memiliki sebuah matriks bilangan bulat $A = (a_{ij})$ berukuran $n \times n$. Untuk setiap $1 \le i, j \le n$:

• Jika $i = j$, $i = 1$, atau $j = 1$, maka $a_{ij} = -1$.
• Selain itu, $a_{ij}$ adalah bilangan bulat tak negatif.

Bantulah VegiCat membentuk sebuah graf sederhana tak berarah $G$ dengan $n$ simpul yang dinomori dari $1$ hingga $n$.

Untuk setiap pasang simpul berbeda $i, j$ dengan $i > 1$ dan $j > 1$, graf tersebut harus memenuhi kondisi berikut: setelah menghapus simpul $i$ dan $j$, beserta semua sisi yang memiliki titik ujung pada salah satu dari kedua simpul tersebut, harus tersisa tepat $a_{ij}$ sisi.

Setiap pasang simpul $i, j$ ditinjau secara terpisah. Artinya, untuk setiap pasangan, mulailah dengan $G$ sebelum simpul atau sisi mana pun dihapus.

Dijamin bahwa setidaknya ada satu graf seperti itu. Jika terdapat beberapa solusi, keluarkan yang mana saja.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 6 \cdot 10^4$), banyaknya kasus uji. Deskripsi dari setiap kasus uji menyusul.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($4 \le n \le 10^3$), yang menyatakan banyaknya simpul pada graf.

Kemudian masing-masing dari $n$ baris berikutnya berisi $n$ bilangan bulat yang dipisahkan spasi $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), yang merepresentasikan matriks $A$ sebagaimana dijelaskan pada soal.

Dijamin bahwa total jumlah $n^2$ di seluruh kasus uji tidak melebihi $1.2 \cdot 10^6$, dan bahwa setidaknya ada satu graf yang bersesuaian dengan matriks $A$.

Keluaran

Untuk setiap kasus uji, keluarkan matriks ketetanggaan dari graf yang Anda bentuk. Keluarkan $n$ baris, masing-masing berisi $n$ bilangan bulat yang dipisahkan spasi. Setiap bilangan bulat harus bernilai $0$ atau $1$. Entri pada baris ke-$i$ dan kolom ke-$j$ bernilai $1$ jika terdapat sisi antara simpul $i$ dan $j$, serta $0$ jika sebaliknya. Jika terdapat beberapa solusi, keluarkan yang mana saja.

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

Matriks masukan yang sebenarnya hanya akan memiliki satu spasi di antara dua bilangan bulat. Spasi tambahan pada sampel dirancang untuk meningkatkan keterbacaan tata letak.