Busy Beaver jouait avec un graphe non orienté, connexe et non pondéré possédant $N$ ($2 \le N \le 500$) sommets numérotés de 1 à $N$. Pour chaque paire de sommets $1 \le i < j \le N$, il a noté sur une serviette la longueur du plus court chemin $A_{i,j}$ entre le sommet $i$ et le sommet $j$. Réalisant que tous ces nombres prenaient trop de place sur sa serviette, Busy Beaver a décidé de ne noter que $B_{i,j}$, les valeurs de $A_{i,j} \pmod 5$.

Maintenant, Busy Beaver a égaré son graphe et ne possède plus que sa serviette avec les valeurs de $B_{i,j}$ écrites dessus. Aidez Busy Beaver à reconstruire un graphe possible, ou déterminez qu'aucun graphe de ce type n'existe et qu'il a fait une erreur.

Formellement, étant donné $N$ et $B_{i,j}$ avec $0 \le B_{i,j} < 5$, déterminez s'il existe un graphe non orienté, connexe et non pondéré à $N$ sommets tel que la longueur du plus court chemin entre les sommets $i$ et $j$ soit congru à $B_{i,j} \pmod 5$. Si un tel graphe existe, affichez n'importe quel graphe possible.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient un entier unique $t$ ($1 \le t \le 100$) : le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier positif unique $N$.

Ensuite, $N - 1$ lignes suivent. La $i$-ième de ces lignes contient $N - i$ entiers positifs séparés par des espaces. Le $j$-ième entier sur la $i$-ième ligne représente $B_{i,j+i}$.

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas 500.

Sortie

Pour chaque cas de test, affichez "YES" s'il existe un graphe possible, ou "NO" si aucun graphe de ce type n'existe. Vous pouvez afficher la réponse en majuscules ou en minuscules. Par exemple, les chaînes "yEs", "yes", "Yes" et "YES" seront reconnues comme des réponses positives.

Si votre programme répond "YES", affichez $N - 1$ lignes supplémentaires. La $i$-ième de ces lignes doit contenir $N - i$ entiers positifs. Le $j$-ième entier sur la $i$-ième ligne doit être 1 s'il doit y avoir une arête entre le sommet $i$ et le sommet $i + j$, et 0 sinon.

Sous-tâches

Vous recevrez 25 % des points pour chaque sous-tâche si les réponses YES/NO sont correctes, mais que le graphe fourni est incorrect. Pour chaque cas de test avec une réponse "YES", vous devez afficher exactement $N - 1$ lignes avec la $i$-ième ligne contenant $N - i$ entiers (qui sont 0 ou 1) pour obtenir des points partiels.

• (20 points) : La somme de $N$ sur tous les cas de test ne dépasse pas 10.
• (80 points) : Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

YES
1 1
1
YES
0 1
1
NO

Remarque

Dans le premier cas de test, il y a 3 sommets et les distances les plus courtes entre toute paire de sommets sont 1 (mod 5). Ceci est réalisable en construisant un graphe avec 3 sommets et une arête entre chaque paire de sommets.

Dans le deuxième cas de test, il y a 3 sommets et la distance la plus courte entre les sommets 1 et 2 est 2 (mod 5), et la distance la plus courte entre les sommets 1 et 3 ainsi qu'entre les sommets 2 et 3 sont toutes deux 1 (mod 5). Ceci est réalisable en construisant un graphe avec 3 sommets et une arête entre les sommets 1 et 3 ainsi qu'entre les sommets 2 et 3.

Dans le troisième cas de test, il y a 3 sommets et les distances les plus courtes entre toute paire de sommets sont 0 (mod 5). On peut montrer qu'aucun graphe non pondéré, non orienté et connexe ne peut satisfaire ce cas de test.