Il existe une machine de transformation de chaînes qui traite spécifiquement les chaînes $\texttt{01}$, et qui possède en interne un ensemble fini prédéfini de règles $\mathcal{R}$. Chaque règle est de la forme $(u, v)$, où $u, v$ sont des chaînes $\texttt{01}$ non vides de même longueur, ce qui signifie qu'en une étape d'opération, on peut choisir une sous-chaîne $u$ de la chaîne courante et la remplacer par $v$. Chaque fois que l'on fournit à la machine une paire de chaînes $\texttt{01}$ non vides de même longueur $(s, t)$, la machine affiche le nombre minimal d'étapes d'opération nécessaires pour transformer $s$ en $t$, ou signale qu'il n'y a pas de solution.

Vous vous souvenez avoir autrefois fourni à cette machine $n$ paires de chaînes $\texttt{01}$ non vides de même longueur $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$. Par coïncidence, dans vos souvenirs, chaque requête avait non seulement une solution, mais vérifiait également que le nombre minimal d'étapes d'opération était $d_i \leqslant 2$.

Afin de vérifier si votre mémoire vous fait défaut, veuillez déterminer s'il existe un ensemble de règles $\mathcal{R}$ tel que les sorties réelles de la machine pour ces $n$ entrées soient totalement cohérentes avec vos souvenirs.

Entrée

La première ligne contient un entier strictement positif $T$, représentant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier strictement positif $n$, représentant le nombre d'enregistrements de requêtes. Dans les $n$ lignes suivantes, la $i$-ème ligne contient deux chaînes $\texttt{01}$ non vides de même longueur $s_i, t_i$ et un entier $d_i$ ($0 \leqslant d_i \leqslant 2$), représentant respectivement la chaîne initiale, la chaîne cible et le nombre minimal d'étapes d'opération donné par la machine lors de la $i$-ème entrée.

Sortie

Pour chaque cas de test, affichez une chaîne de caractères sur une ligne. S'il existe un ensemble de règles $\mathcal{R}$ satisfaisant les conditions, affichez YES ; sinon, affichez NO.

Vous pouvez afficher YES et NO dans n'importe quelle casse ; par exemple, yes, Yes ou YES seront tous considérés comme la même réponse.

Exemples

Entrée 1

3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2

Sortie 1

YES
NO
NO

Remarque

• Cas de test $1$ : On peut construire un ensemble ne contenant qu'une seule règle $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$ :
  • Pour la $1$-re requête, $s_1 = t_1 = \texttt{010}$, aucune opération n'est nécessaire pour effectuer la transformation, et le nombre minimal d'étapes d'opération est $0$.
  • Pour la $2$-e requête, en remplaçant le suffixe $\texttt{01}$ de $\texttt{001}$ par $\texttt{10}$, on obtient $\texttt{010}$ en $1$ étape.
  • Pour la $3$-e requête, comme $\texttt{001}$ et $\texttt{100}$ diffèrent à la fois à la $1$-re et à la $3$-e position, une règle de longueur $2$ seule ne permet pas d'effectuer la transformation en $1$ étape ; en revanche, on peut d'abord remplacer le suffixe $\texttt{01}$ de la chaîne initiale $\texttt{001}$ par $\texttt{10}$ pour obtenir la chaîne intermédiaire $\texttt{010}$, puis remplacer le préfixe $\texttt{01}$ de la chaîne intermédiaire $\texttt{010}$ par $\texttt{10}$ pour obtenir la chaîne cible $\texttt{100}$, de sorte que le nombre minimal d'étapes d'opération est $2$.
• Cas de test $2$ : Pour transformer $\texttt{10}$ en $\texttt{01}$ en $1$ étape, l'ensemble de règles $\mathcal{R}$ doit nécessairement contenir la règle $(\texttt{10}, \texttt{01})$. Cependant, dès que cette règle est incluse, la $2$-e requête n'a besoin que de remplacer le préfixe $\texttt{10}$ de $\texttt{100}$ par $\texttt{01}$ pour obtenir $\texttt{010}$ en $1$ étape, ce qui contredit $d_2 = 2$ dans vos souvenirs.
• Cas de test $3$ : Toutes les chaînes au cours du processus de transformation doivent être des chaînes $\texttt{01}$ de même longueur. Il n'existe que deux chaînes $\texttt{01}$ de longueur $1$, à savoir $\texttt{0}$ et $\texttt{1}$. Si l'on peut transformer $\texttt{0}$ en $\texttt{1}$, alors la règle $(\texttt{0}, \texttt{1})$ existe nécessairement et $1$ seule étape suffit pour terminer, il est donc impossible qu'il faille au minimum $2$ étapes.

Contraintes

Pour toutes les données de test, il est garanti que $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, et que $s_i, t_i$ sont toutes deux des chaînes composées uniquement des caractères $\texttt{0}$ et $\texttt{1}$.

En notant $L = \sum_{i=1}^{n} |s_i|$ la somme des longueurs de toutes les chaînes initiales d'un même cas de test, et $\sum L$ la somme de $L$ sur tous les cas de test d'un même fichier de test, il est garanti que $\sum L \leqslant 3\times 10^6$.

Ce problème active des dépendances raisonnables entre les sous-tâches.

• Propriété particulière A : Il est garanti que pour tout $1 \leqslant i \leqslant n$, on a $|s_i| \geqslant 50$.