Det finns en strängomvandlingsmaskin som specifikt bearbetar $\texttt{01}$-strängar och som internt har en förinställd ändlig mängd regler $\mathcal{R}$. Varje regel har formen $(u, v)$, där $u, v$ är icke-tomma $\texttt{01}$-strängar av samma längd, vilket innebär att man i ett operationssteg kan välja en delsträng $u$ av den aktuella strängen och ersätta den med $v$. Varje gång ett par av icke-tomma $\texttt{01}$-strängar av samma längd $(s, t)$ matas in i maskinen, skriver maskinen ut det minsta antalet operationssteg som krävs för att omvandla $s$ till $t$, eller rapporterar att det saknas lösning.

Du minns att du en gång matade in $n$ par av icke-tomma $\texttt{01}$-strängar av samma längd $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ i denna maskin. Av en händelse hade, enligt ditt minne, varje fråga inte bara en lösning, utan uppfyllde dessutom att det minsta antalet operationssteg var $d_i \leqslant 2$.

För att kontrollera om ditt minne sviker dig, avgör: finns det en regelmängd $\mathcal{R}$ sådan att maskinens faktiska utdata för dessa $n$ indata helt stämmer överens med ditt minne?

Indata

Den första raden innehåller ett positivt heltal $T$, som anger antalet testfall.

För varje testfall innehåller den första raden ett positivt heltal $n$, som anger antalet frågeposter. På de följande $n$ raderna innehåller den $i$-te raden två icke-tomma $\texttt{01}$-strängar av samma längd $s_i, t_i$ och ett heltal $d_i$ ($0 \leqslant d_i \leqslant 2$), som anger startsträngen, målsträngen respektive det minsta antalet operationssteg som maskinen angav vid den $i$-te inmatningen.

Utdata

För varje testfall, skriv ut en rad med en sträng. Om det finns en regelmängd $\mathcal{R}$ som uppfyller villkoren, skriv ut YES; annars, skriv ut NO.

Du får skriva ut YES och NO med valfri kombination av versaler och gemener; exempelvis räknas yes, Yes och YES som samma svar.

Exempel

Indata 1

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

Utdata 1

YES
NO
NO

Förklaring

• Testfall $1$: Vi kan konstruera en mängd som endast innehåller en regel, $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • För den $1$:a frågan är $s_1 = t_1 = \texttt{010}$, så omvandlingen är klar utan några operationer och det minsta antalet operationssteg är $0$.
  • För den $2$:a frågan kan vi ersätta suffixet $\texttt{01}$ i $\texttt{001}$ med $\texttt{10}$, vilket ger $\texttt{010}$ på $1$ steg.
  • För den $3$:e frågan, eftersom $\texttt{001}$ och $\texttt{100}$ skiljer sig åt på både den $1$:a och den $3$:e positionen, kan en regel av längd $2$ ensam inte slutföra omvandlingen på $1$ steg; däremot kan vi först ersätta suffixet $\texttt{01}$ i startsträngen $\texttt{001}$ med $\texttt{10}$ för att få mellansträngen $\texttt{010}$, och därefter ersätta prefixet $\texttt{01}$ i mellansträngen $\texttt{010}$ med $\texttt{10}$ för att få målsträngen $\texttt{100}$, så det minsta antalet operationssteg är $2$.
• Testfall $2$: För att omvandla $\texttt{10}$ till $\texttt{01}$ på $1$ steg måste regelmängden $\mathcal{R}$ innehålla regeln $(\texttt{10}, \texttt{01})$. Men så snart denna regel ingår, räcker det i den $2$:a frågan att ersätta prefixet $\texttt{10}$ i $\texttt{100}$ med $\texttt{01}$ för att få $\texttt{010}$ på $1$ steg, vilket strider mot $d_2 = 2$ i ditt minne.
• Testfall $3$: Alla strängar under omvandlingsprocessen måste vara $\texttt{01}$-strängar av samma längd. Det finns bara två $\texttt{01}$-strängar av längd $1$, nämligen $\texttt{0}$ och $\texttt{1}$. Om $\texttt{0}$ kan omvandlas till $\texttt{1}$ måste regeln $(\texttt{0}, \texttt{1})$ finnas och det krävs bara $1$ steg för att bli klar, så det är omöjligt att det skulle krävas minst $2$ steg.

Begränsningar

För alla testdata garanteras att $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, samt att både $s_i, t_i$ är strängar som endast består av tecknen $\texttt{0}$ och $\texttt{1}$.

Låt $L = \sum_{i=1}^{n} |s_i|$ vara summan av längderna av alla startsträngar i ett enskilt testfall, och $\sum L$ vara summan av $L$ över alla testfall i en enskild testfil; det garanteras att $\sum L \leqslant 3\times 10^6$.

Rimliga deluppgiftsberoenden är aktiverade för detta problem.

• Särskild egenskap A: Det garanteras att $|s_i| \geqslant 50$ gäller för alla $1 \leqslant i \leqslant n$.