Busy Beaver играл с неориентированным связным невзвешенным графом с $N$ ($2 \le N \le 500$) вершинами, пронумерованными от $1$ до $N$. Для каждой пары вершин $1 \le i < j \le N$ он записал на салфетке длину кратчайшего пути $A_{i,j}$ между вершиной $i$ и вершиной $j$. Поняв, что все эти числа занимают слишком много места на салфетке, Busy Beaver решил записывать только $B_{i,j}$, значения $A_{i,j} \pmod 5$.

Теперь Busy Beaver потерял свой граф и у него осталась только салфетка со значениями $B_{i,j}$. Помогите Busy Beaver восстановить какой-нибудь подходящий граф или определите, что такого графа не существует и он допустил ошибку.

Формально, по заданным $N$ и $B_{i,j}$, где $0 \le B_{i,j} < 5$, определите, существует ли неориентированный связный невзвешенный граф с $N$ вершинами такой, что длина кратчайшего пути между вершинами $i$ и $j$ сравнима с $B_{i,j} \pmod 5$. Если такой граф существует, выведите любой подходящий граф.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке содержится целое число $t$ ($1 \le t \le 100$): количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $N$.

Затем следуют $N - 1$ строк. $i$-я из этих строк содержит $N - i$ целых чисел. $j$-е число в $i$-й строке представляет $B_{i, j+i}$.

Гарантируется, что сумма $N$ по всем наборам входных данных не превышает $500$.

Выходные данные

Для каждого набора входных данных выведите "YES", если существует подходящий граф, или "NO", если такого графа не существует. Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки "yEs", "yes", "Yes" и "YES" будут распознаны как положительные ответы.

Если ваша программа отвечает "YES", выведите дополнительные $N - 1$ строк. $i$-я из этих строк должна содержать $N - i$ целых чисел. $j$-е число в $i$-й строке должно быть равно $1$, если между вершиной $i$ и вершиной $i + j$ должно быть ребро, и $0$ в противном случае.

Оценивание

Вы получите 25% баллов за каждую подзадачу, если ответы YES/NO верны, но предоставленный граф неверен. Для каждого набора входных данных с ответом "YES" вы должны вывести ровно $N - 1$ строк, где $i$-я строка содержит $N - i$ целых чисел (равных $0$ или $1$), чтобы получить частичные баллы.

• (20 баллов): Сумма $N$ по всем наборам входных данных не превышает $10$.
• (80 баллов): Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

YES
1 1
1
YES
0 1
1
NO

Примечание

В первом наборе входных данных $3$ вершины, и кратчайшие расстояния между любой парой вершин равны $1 \pmod 5$. Это достижимо путем построения графа с $3$ вершинами и ребром между любой парой вершин.

Во втором наборе входных данных $3$ вершины, кратчайшее расстояние между вершинами $1$ и $2$ равно $2 \pmod 5$, а кратчайшие расстояния между вершинами $1$ и $3$, а также между $2$ и $3$ равны $1 \pmod 5$. Это достижимо путем построения графа с $3$ вершинами и ребрами между вершинами $1$ и $3$, а также между $2$ и $3$.

В третьем наборе входных данных $3$ вершины, и кратчайшие расстояния между любой парой вершин равны $0 \pmod 5$. Можно показать, что ни один невзвешенный, неориентированный, связный граф не может удовлетворять условиям этого теста.