VegiCat ma macierz liczb całkowitych $A = (a_{ij})$ o wymiarach $n \times n$. Dla każdych $1 \le i, j \le n$:

• Jeśli $i = j$, $i = 1$ lub $j = 1$, to $a_{ij} = -1$.
• W przeciwnym razie $a_{ij}$ jest nieujemną liczbą całkowitą.

Pomóż VegiCatowi skonstruować nieskierowany graf prosty $G$ o $n$ wierzchołkach, ponumerowanych od $1$ do $n$.

Dla każdej pary różnych wierzchołków $i, j$ takich, że $i > 1$ oraz $j > 1$, graf musi spełniać następujący warunek: po usunięciu wierzchołków $i$ oraz $j$ wraz ze wszystkimi krawędziami mającymi koniec w którymkolwiek z tych dwóch wierzchołków, musi pozostać dokładnie $a_{ij}$ krawędzi.

Każda para wierzchołków $i, j$ jest rozpatrywana osobno. Oznacza to, że dla każdej pary zaczynamy od grafu $G$ sprzed usunięcia jakichkolwiek wierzchołków lub krawędzi.

Gwarantuje się, że istnieje co najmniej jeden taki graf. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 6 \cdot 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera liczbę całkowitą $n$ ($4 \le n \le 10^3$), oznaczającą liczbę wierzchołków w grafie.

Następnie każdy z kolejnych $n$ wierszy zawiera $n$ oddzielonych spacjami liczb całkowitych $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), reprezentujących macierz $A$ opisaną w treści zadania.

Gwarantuje się, że łączna suma $n^2$ po wszystkich przypadkach testowych nie przekracza $1.2 \cdot 10^6$ oraz że istnieje co najmniej jeden graf odpowiadający macierzy $A$.

Wyjście

Dla każdego przypadku testowego wypisz macierz sąsiedztwa skonstruowanego grafu. Wypisz $n$ wierszy, z których każdy zawiera $n$ liczb całkowitych oddzielonych spacjami. Każda liczba musi być równa $0$ lub $1$. Element w $i$-tym wierszu i $j$-tej kolumnie wynosi $1$, jeśli między wierzchołkami $i$ oraz $j$ istnieje krawędź, a $0$ w przeciwnym razie. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 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

Wyjście 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

Uwagi

Rzeczywista macierz wejściowa będzie miała tylko pojedynczą spację między dwiema liczbami całkowitymi. Dodatkowe spacje w przykładzie mają na celu poprawę czytelności układu.