Busy Beaver bawił się nieskierowanym, spójnym, nieważonym grafem o $N$ ($2 \le N \le 500$) wierzchołkach ponumerowanych od $1$ do $N$. Dla każdej pary wierzchołków $1 \le i < j \le N$ zapisał na serwetce długość najkrótszej ścieżki $A_{i,j}$ między wierzchołkiem $i$ a wierzchołkiem $j$. Zdając sobie sprawę, że wszystkie te liczby zajmują zbyt wiele miejsca na serwetce, Busy Beaver postanowił zapisać tylko $B_{i,j}$, czyli wartości $A_{i,j} \pmod 5$.

Teraz Busy Beaver zgubił swój graf i ma tylko serwetkę z zapisanymi wartościami $B_{i,j}$. Pomóż Busy Beaverowi odtworzyć możliwy graf lub ustal, że taki graf nie istnieje i że popełnił błąd.

Formalnie, mając dane $N$ oraz $B_{i,j}$, gdzie $0 \le B_{i,j} < 5$, rozstrzygnij, czy istnieje nieskierowany, spójny, nieważony graf o $N$ wierzchołkach taki, że długość najkrótszej ścieżki między wierzchołkami $i$ oraz $j$ jest przystająca do $B_{i,j} \pmod 5$. Jeśli taki graf istnieje, wypisz dowolny możliwy graf.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera pojedynczą liczbę całkowitą $t$ ($1 \le t \le 100$): liczbę przypadków testowych. Następnie następuje opis przypadków testowych.

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $N$.

Następnie następuje $N - 1$ linii wejścia. $i$-ta z tych linii zawiera $N - i$ oddzielonych spacjami liczb całkowitych. $j$-ta liczba w $i$-tej linii reprezentuje $B_{i,j+i}$.

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $500$.

Wyjście

Dla każdego przypadku testowego wypisz "YES", jeśli istnieje możliwy graf, lub "NO", jeśli taki graf nie istnieje. Odpowiedź można wypisać w dowolnej wielkości liter (wielkie lub małe). Na przykład ciągi "yEs", "yes", "Yes" oraz "YES" zostaną rozpoznane jako odpowiedzi pozytywne.

Jeśli Twój program odpowie "YES", wypisz dodatkowe $N - 1$ linii. $i$-ta z tych linii powinna zawierać $N - i$ liczb całkowitych. $j$-ta liczba w $i$-tej linii powinna wynosić $1$, jeśli powinna istnieć krawędź między wierzchołkiem $i$ a wierzchołkiem $i + j$, oraz $0$ w przeciwnym razie.

Punktacja

Otrzymasz 25% punktów za każde podzadanie, jeśli odpowiedzi YES/NO są poprawne, ale dostarczony graf jest niepoprawny. Dla każdego przypadku testowego z odpowiedzią "YES", musisz wypisać dokładnie $N - 1$ linii, gdzie $i$-ta linia zawiera $N - i$ liczb (będących $0$ lub $1$), aby otrzymać punkty częściowe.

• (20 punktów): Suma $N$ we wszystkich przypadkach testowych nie przekracza $10$.
• (80 punktów): Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3
3
1 1
1
3
2 1
1
3
0 0
0

Wyjście 1

YES
1 1
1
YES
0 1
1
NO

Uwagi

W pierwszym przypadku testowym mamy 3 wierzchołki, a najkrótsze odległości między każdą parą wierzchołków wynoszą $1 \pmod 5$. Jest to możliwe do osiągnięcia poprzez skonstruowanie grafu o 3 wierzchołkach z krawędzią między każdą parą wierzchołków.

W drugim przypadku testowym mamy 3 wierzchołki, najkrótsza odległość między wierzchołkiem 1 i 2 wynosi $2 \pmod 5$, a najkrótsza odległość między wierzchołkiem 1 i 3 oraz między wierzchołkiem 2 i 3 wynosi $1 \pmod 5$. Jest to możliwe do osiągnięcia poprzez skonstruowanie grafu o 3 wierzchołkach z krawędzią między wierzchołkami 1 i 3 oraz między wierzchołkami 2 i 3.

W trzecim przypadku testowym mamy 3 wierzchołki, a najkrótsze odległości między każdą parą wierzchołków wynoszą $0 \pmod 5$. Można wykazać, że żaden nieważony, nieskierowany, spójny graf nie może spełnić warunków tego przypadku testowego.