Terdapat sebuah mesin transformasi string yang khusus memproses string $\texttt{01}$, yang di dalamnya telah diatur sebuah himpunan berhingga $\mathcal{R}$ yang berisi sejumlah aturan. Setiap aturan berbentuk $(u, v)$, dengan $u, v$ adalah string $\texttt{01}$ tak kosong dengan panjang yang sama, yang berarti dalam satu langkah operasi, kita dapat memilih sebuah substring $u$ dari string saat ini dan menggantinya dengan $v$. Setiap kali sepasang string $\texttt{01}$ tak kosong dengan panjang yang sama $(s, t)$ dimasukkan ke dalam mesin, mesin akan mengeluarkan jumlah langkah operasi minimum yang diperlukan untuk mengubah $s$ menjadi $t$, atau melaporkan bahwa tidak ada solusi.

Anda teringat bahwa Anda pernah memasukkan $n$ pasang string $\texttt{01}$ tak kosong dengan panjang yang sama $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ ke dalam mesin ini. Secara kebetulan, dalam ingatan Anda, setiap kueri tidak hanya memiliki solusi, tetapi juga memenuhi bahwa jumlah langkah operasi minimum adalah $d_i \leqslant 2$.

Untuk memverifikasi apakah ingatan Anda keliru, tentukanlah: apakah terdapat sebuah himpunan aturan $\mathcal{R}$ sehingga keluaran aktual mesin untuk $n$ masukan ini sepenuhnya sesuai dengan ingatan Anda?

Masukan

Baris pertama berisi sebuah bilangan bulat positif $T$, yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat positif $n$, yang menyatakan jumlah catatan kueri. Pada $n$ baris berikutnya, baris ke-$i$ berisi dua string $\texttt{01}$ tak kosong dengan panjang yang sama $s_i, t_i$ dan sebuah bilangan bulat $d_i$ ($0 \leqslant d_i \leqslant 2$), yang masing-masing menyatakan string awal, string target, serta jumlah langkah operasi minimum yang diberikan oleh mesin pada masukan ke-$i$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah string. Jika terdapat himpunan aturan $\mathcal{R}$ yang memenuhi syarat, keluarkan YES; jika tidak, keluarkan NO.

Anda dapat mengeluarkan YES dan NO dalam kombinasi huruf besar atau kecil apa pun; misalnya yes, Yes, atau YES semuanya akan dianggap sebagai jawaban yang sama.

Contoh

Masukan 1

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

Keluaran 1

YES
NO
NO

Catatan

• Kasus uji ke-$1$: Kita dapat membentuk himpunan yang hanya berisi satu aturan $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • Untuk kueri ke-$1$, $s_1 = t_1 = \texttt{010}$, transformasi selesai tanpa memerlukan operasi apa pun, sehingga jumlah langkah operasi minimum adalah $0$.
  • Untuk kueri ke-$2$, mengganti sufiks $\texttt{01}$ dari $\texttt{001}$ dengan $\texttt{10}$ akan menghasilkan $\texttt{010}$ dalam $1$ langkah.
  • Untuk kueri ke-$3$, karena $\texttt{001}$ dan $\texttt{100}$ berbeda pada posisi ke-$1$ maupun posisi ke-$3$, aturan dengan panjang $2$ saja tidak dapat menyelesaikan transformasi dalam $1$ langkah; namun kita dapat terlebih dahulu mengganti sufiks $\texttt{01}$ dari string awal $\texttt{001}$ dengan $\texttt{10}$ untuk mendapatkan string perantara $\texttt{010}$, lalu mengganti prefiks $\texttt{01}$ dari string perantara $\texttt{010}$ dengan $\texttt{10}$ untuk mendapatkan string target $\texttt{100}$, sehingga jumlah langkah operasi minimum adalah $2$.
• Kasus uji ke-$2$: Untuk mengubah $\texttt{10}$ menjadi $\texttt{01}$ dalam $1$ langkah, himpunan aturan $\mathcal{R}$ harus memuat aturan $(\texttt{10}, \texttt{01})$. Namun begitu aturan tersebut dimuat, kueri ke-$2$ hanya perlu mengganti prefiks $\texttt{10}$ dari $\texttt{100}$ dengan $\texttt{01}$ untuk mendapatkan $\texttt{010}$ dalam $1$ langkah, yang bertentangan dengan $d_2 = 2$ dalam ingatan Anda.
• Kasus uji ke-$3$: Semua string selama proses transformasi harus merupakan string $\texttt{01}$ dengan panjang yang sama. String $\texttt{01}$ dengan panjang $1$ hanya ada dua macam, yaitu $\texttt{0}$ dan $\texttt{1}$. Jika $\texttt{0}$ dapat diubah menjadi $\texttt{1}$, maka aturan $(\texttt{0}, \texttt{1})$ pasti ada dan hanya memerlukan $1$ langkah untuk selesai, sehingga tidak mungkin memerlukan sedikitnya $2$ langkah.

Batasan

Untuk semua data uji, dijamin bahwa $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, dan baik $s_i, t_i$ merupakan string yang hanya terdiri dari karakter $\texttt{0}$ dan $\texttt{1}$.

Misalkan $L = \sum_{i=1}^{n} |s_i|$ menyatakan jumlah panjang semua string awal dalam satu kasus uji, dan $\sum L$ menyatakan jumlah $L$ dari seluruh kasus uji dalam satu berkas uji; dijamin bahwa $\sum L \leqslant 3\times 10^6$.

Soal ini menggunakan ketergantungan subsoal yang wajar.

• Sifat Khusus A: Dijamin bahwa untuk semua $1 \leqslant i \leqslant n$, berlaku $|s_i| \geqslant 50$.