Det finnes en strengtransformasjonsmaskin som spesifikt behandler $\texttt{01}$-strenger, og som internt har en forhåndsinnstilt endelig mengde regler $\mathcal{R}$. Hver regel har formen $(u, v)$, der $u, v$ er ikke-tomme $\texttt{01}$-strenger av lik lengde, noe som betyr at man i ett operasjonssteg kan velge en delstreng $u$ av den nåværende strengen og erstatte den med $v$. Hver gang et par av ikke-tomme $\texttt{01}$-strenger av lik lengde $(s, t)$ mates inn i maskinen, skriver maskinen ut det minste antallet operasjonssteg som kreves for å transformere $s$ til $t$, eller rapporterer at det ikke finnes noen løsning.

Du husker at du en gang matet inn $n$ par av ikke-tomme $\texttt{01}$-strenger av lik lengde $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ i denne maskinen. Tilfeldigvis hadde, ifølge hukommelsen din, hver spørring ikke bare en løsning, men oppfylte også at det minste antallet operasjonssteg var $d_i \leqslant 2$.

For å sjekke om hukommelsen din svikter, avgjør følgende: finnes det en regelmengde $\mathcal{R}$ slik at maskinens faktiske utdata for disse $n$ inndataene stemmer fullstendig overens med hukommelsen din?

Inndata

Den første linjen inneholder et positivt heltall $T$, som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et positivt heltall $n$, som angir antallet spørringsoppføringer. På de neste $n$ linjene inneholder den $i$-te linjen to ikke-tomme $\texttt{01}$-strenger av lik lengde $s_i, t_i$ og et heltall $d_i$ ($0 \leqslant d_i \leqslant 2$), som angir henholdsvis startstrengen, målstrengen og det minste antallet operasjonssteg oppgitt av maskinen ved den $i$-te inndataen.

Utdata

For hvert testtilfelle, skriv ut én linje med én streng. Hvis det finnes en regelmengde $\mathcal{R}$ som oppfyller betingelsene, skriv ut YES; ellers, skriv ut NO.

Du kan skrive ut YES og NO med en hvilken som helst kombinasjon av store og små bokstaver; for eksempel vil yes, Yes og YES alle bli regnet som det samme svaret.

Eksempler

Inndata 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

Forklaring

• Testtilfelle $1$: Vi kan konstruere en mengde som kun inneholder én regel, $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • For den $1$. spørringen er $s_1 = t_1 = \texttt{010}$, så transformasjonen fullføres uten noen operasjoner, og det minste antallet operasjonssteg er $0$.
  • For den $2$. spørringen kan vi erstatte suffikset $\texttt{01}$ i $\texttt{001}$ med $\texttt{10}$, og dermed få $\texttt{010}$ på $1$ steg.
  • For den $3$. spørringen, ettersom $\texttt{001}$ og $\texttt{100}$ er forskjellige både på den $1$. og den $3$. posisjonen, kan ikke en regel av lengde $2$ alene fullføre transformasjonen på $1$ steg; men vi kan først erstatte suffikset $\texttt{01}$ i startstrengen $\texttt{001}$ med $\texttt{10}$ for å få mellomstrengen $\texttt{010}$, og deretter erstatte prefikset $\texttt{01}$ i mellomstrengen $\texttt{010}$ med $\texttt{10}$ for å få målstrengen $\texttt{100}$, så det minste antallet operasjonssteg er $2$.
• Testtilfelle $2$: For å transformere $\texttt{10}$ til $\texttt{01}$ på $1$ steg, må regelmengden $\mathcal{R}$ inneholde regelen $(\texttt{10}, \texttt{01})$. Men så snart denne regelen er inkludert, trenger den $2$. spørringen bare å erstatte prefikset $\texttt{10}$ i $\texttt{100}$ med $\texttt{01}$ for å oppnå $\texttt{010}$ på $1$ steg, noe som motsier $d_2 = 2$ i hukommelsen din.
• Testtilfelle $3$: Alle strenger under transformasjonsprosessen må være $\texttt{01}$-strenger av lik lengde. Det finnes bare to $\texttt{01}$-strenger av lengde $1$, nemlig $\texttt{0}$ og $\texttt{1}$. Hvis man kan transformere $\texttt{0}$ til $\texttt{1}$, må regelen $(\texttt{0}, \texttt{1})$ nødvendigvis eksistere og det kreves bare $1$ steg for å fullføre, så det er umulig at det kreves minst $2$ steg.

Begrensninger

For alle testdata garanteres det at $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, og at både $s_i, t_i$ er strenger som kun består av tegnene $\texttt{0}$ og $\texttt{1}$.

La $L = \sum_{i=1}^{n} |s_i|$ være summen av lengdene til alle startstrengene i ett enkelt testtilfelle, og la $\sum L$ være summen av $L$ over alle testtilfellene i én enkelt testfil; det garanteres at $\sum L \leqslant 3\times 10^6$.

Rimelige deloppgaveavhengigheter er aktivert for denne oppgaven.

• Spesiell egenskap A: Det garanteres at $|s_i| \geqslant 50$ gjelder for alle $1 \leqslant i \leqslant n$.