У VegiCat є цілочисельна матриця $A = (a_{ij})$ розміру $n \times n$. Для всіх $1 \le i, j \le n$:
- Якщо $i = j$, $i = 1$ або $j = 1$, то $a_{ij} = -1$.
- Інакше $a_{ij}$ — невід'ємне ціле число.
Допоможіть VegiCat побудувати неорієнтований простий граф $G$ з $n$ вершинами, пронумерованими від $1$ до $n$.
Для кожної пари різних вершин $i, j$ з $i > 1$ та $j > 1$ граф повинен задовольняти таку умову: після видалення вершин $i$ та $j$ разом з усіма ребрами, які мають кінець у будь-якій із цих вершин, має залишитися рівно $a_{ij}$ ребер.
Кожна пара вершин $i, j$ розглядається окремо. Тобто для кожної пари ми починаємо з початкового графа $G$ до видалення будь-яких вершин або ребер.
Гарантується, що принаймні один такий граф існує. Якщо розв'язків декілька, виведіть будь-який із них.
Вхідні дані
Перший рядок містить ціле число $T$ ($1 \le T \le 6 \cdot 10^4$) — кількість наборів вхідних даних. Далі йде опис наборів вхідних даних.
Для кожного набору вхідних даних перший рядок містить ціле число $n$ ($4 \le n \le 10^3$), що позначає кількість вершин у графі.
Потім кожен із наступних $n$ рядків містить $n$ розділених пробілами цілих чисел $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), які задають матрицю $A$, описану в умові.
Гарантується, що загальна сума $n^2$ за всіма наборами вхідних даних не перевищує $1.2 \cdot 10^6$, і що існує принаймні один граф, який відповідає матриці $A$.
Вихідні дані
Для кожного набору вхідних даних виведіть матрицю суміжності побудованого вами графа. Виведіть $n$ рядків, кожен з яких містить $n$ цілих чисел, розділених пробілами. Кожне число має дорівнювати $0$ або $1$. Елемент у $i$-му рядку та $j$-му стовпці дорівнює $1$, якщо між вершинами $i$ та $j$ є ребро, і $0$ в іншому разі. Якщо розв'язків декілька, виведіть будь-який із них.
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
У реальній вхідній матриці між двома цілими числами буде лише один пробіл. Додаткові пробіли в прикладі призначені для покращення читабельності макета.