Busy Beaver estaba jugando con un grafo no dirigido, conexo y sin pesos con $N$ ($2 \le N \le 500$) vértices numerados del 1 al $N$. Para cada par de vértices $1 \le i < j \le N$, anotó en una servilleta la longitud del camino más corto $A_{i,j}$ desde el vértice $i$ hasta el vértice $j$. Al darse cuenta de que todos estos números ocupaban demasiado espacio en su servilleta, Busy Beaver decidió anotar solo $B_{i,j}$, los valores de $A_{i,j} \pmod 5$.

Ahora, Busy Beaver ha extraviado su grafo y solo tiene su servilleta con los valores de $B_{i,j}$ escritos en ella. Ayuda a Busy Beaver a reconstruir un posible grafo, o determina que no existe tal grafo y que cometió un error.

Formalmente, dados $N$ y $B_{i,j}$ con $0 \le B_{i,j} < 5$, decide si existe un grafo no dirigido, conexo y sin pesos con $N$ vértices tal que la longitud del camino más corto entre los vértices $i$ y $j$ sea congruente con $B_{i,j} \pmod 5$. Si existe tal grafo, imprime cualquier grafo posible.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ ($1 \le t \le 100$): el número de casos de prueba. A continuación, se describen los casos de prueba.

La primera línea de entrada contiene un único entero positivo $N$.

Luego, seguirán $N - 1$ líneas de entrada. La $i$-ésima de estas líneas contendrá $N - i$ enteros positivos separados por espacios. El $j$-ésimo entero en la $i$-ésima línea representa $B_{i,j+i}$.

Se garantiza que la suma de $N$ en todos los casos de prueba no es mayor que 500.

Salida

Para cada caso de prueba, imprime "YES" si existe un grafo posible, o "NO" si no existe tal grafo. Puedes imprimir la respuesta en cualquier combinación de mayúsculas y minúsculas. Por ejemplo, las cadenas "yEs", "yes", "Yes" y "YES" serán reconocidas como respuestas positivas.

Si tu programa responde "YES", imprime $N - 1$ líneas adicionales. La $i$-ésima de estas líneas debe contener $N - i$ enteros. El $j$-ésimo entero en la $i$-ésima línea debe ser 1 si debe haber una arista entre el vértice $i$ y el vértice $i + j$, y 0 en caso contrario.

Scoring

Recibirás el 25% de los puntos por cada subtarea si las respuestas YES/NO son correctas, pero el grafo proporcionado es incorrecto. Para cada caso de prueba con una respuesta "YES", debes imprimir exactamente $N - 1$ líneas con la $i$-ésima línea conteniendo $N - i$ enteros (que sean 0 o 1) para obtener crédito parcial.

• (20 puntos): La suma de $N$ en todos los casos de prueba no excede 10.
• (80 puntos): Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

YES
1 1
1
YES
0 1
1
NO

Nota

En el primer caso de prueba, hay 3 vértices y las distancias más cortas entre cualquier par de vértices es 1 (mod 5). Esto es posible construyendo un grafo con 3 vértices y una arista entre cualquier par de vértices.

En el segundo caso de prueba, hay 3 vértices y las distancias más cortas entre el vértice 1 y 2 es 2 (mod 5), y la distancia más corta entre el vértice 1 y 3, así como entre el vértice 2 y 3, son ambas 1 (mod 5). Esto es posible construyendo un grafo con 3 vértices y una arista entre los vértices 1 y 3, así como entre los vértices 2 y 3.

En el tercer caso de prueba, hay 3 vértices y las distancias más cortas entre cualquier par de vértices es 0 (mod 5). Se puede demostrar que ningún grafo no dirigido, conexo y sin pesos puede satisfacer este caso de prueba.