$\texttt{01}$ 文字列を専門に処理する文字列変換機があり、その内部にはいくつかの規則からなる有限集合 $\mathcal{R}$ があらかじめ設定されている。各規則は $(u, v)$ の形をしており、ここで $u, v$ は空でない同じ長さの $\texttt{01}$ 文字列であり、一回の操作で現在の文字列の部分文字列 $u$ を一つ選び、それを $v$ に置き換えられることを表す。空でない同じ長さの $\texttt{01}$ 文字列の組 $(s, t)$ を機械に入力するたびに、機械は $s$ を $t$ に変換するのに必要な最小の操作回数を出力するか、変換不可能であると報告する。

あなたは以前、この機械に $n$ 組の空でない同じ長さの $\texttt{01}$ 文字列 $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ を入力したことを思い出した。偶然にも、あなたの記憶では、各クエリには必ず解が存在し、さらに最小操作回数が $d_i \leqslant 2$ を満たしていた。

記憶違いがないか確かめるため、機械のこれら $n$ 個の入力に対する実際の出力があなたの記憶と完全に一致するような規則集合 $\mathcal{R}$ が存在するかどうかを判定せよ。

入力

最初の行には、テストケースの数を表す正の整数 $T$ が与えられる。

各テストケースについて、最初の行にはクエリ記録の数を表す正の整数 $n$ が与えられる。続く $n$ 行のうち $i$ 行目には、空でない同じ長さの二つの $\texttt{01}$ 文字列 $s_i, t_i$ と整数 $d_i$（$0 \leqslant d_i \leqslant 2$）が与えられ、それぞれ $i$ 回目の入力における初期文字列、目標文字列、および機械が出力した最小操作回数を表す。

出力

各テストケースについて、文字列を一行に出力せよ。条件を満たす規則集合 $\mathcal{R}$ が存在する場合は YES を、そうでない場合は NO を出力せよ。

YES と NO は大文字・小文字を問わず出力してよい。例えば yes、Yes、YES はいずれも同じ答えとして扱われる。

入出力例

入力 1

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

出力 1

YES
NO
NO

注記

• 第 $1$ テストケース：一つの規則のみを含む集合 $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$ を構成できる：
  • 第 $1$ クエリでは、$s_1 = t_1 = \texttt{010}$ であるため、一度も操作を行うことなく変換が完了し、最小操作回数は $0$ である。
  • 第 $2$ クエリでは、$\texttt{001}$ の接尾辞 $\texttt{01}$ を $\texttt{10}$ に置き換えることで、$1$ 回の操作で $\texttt{010}$ を得ることができる。
  • 第 $3$ クエリでは、$\texttt{001}$ と $\texttt{100}$ は $1$ 文字目と $3$ 文字目の両方が異なるため、長さ $2$ の規則だけでは $1$ 回の操作で変換を完了できない。しかし、まず初期文字列 $\texttt{001}$ の接尾辞 $\texttt{01}$ を $\texttt{10}$ に置き換えて中間文字列 $\texttt{010}$ を得てから、中間文字列 $\texttt{010}$ の接頭辞 $\texttt{01}$ を $\texttt{10}$ に置き換えて目標文字列 $\texttt{100}$ を得ることができるため、最小操作回数は $2$ である。
• 第 $2$ テストケース：$1$ 回の操作で $\texttt{10}$ を $\texttt{01}$ に変換するためには、規則集合 $\mathcal{R}$ に規則 $(\texttt{10}, \texttt{01})$ が含まれていなければならない。しかしこの規則が含まれていると、第 $2$ クエリでは $\texttt{100}$ の接頭辞 $\texttt{10}$ を $\texttt{01}$ に置き換えるだけで $1$ 回の操作で $\texttt{010}$ が得られてしまい、記憶にある $d_2 = 2$ と矛盾する。
• 第 $3$ テストケース：変換過程におけるすべての文字列は同じ長さの $\texttt{01}$ 文字列でなければならない。長さ $1$ の $\texttt{01}$ 文字列は $\texttt{0}$ と $\texttt{1}$ の二種類しかなく、もし $\texttt{0}$ から $\texttt{1}$ へ変換できるならば、必ず規則 $(\texttt{0}, \texttt{1})$ が存在し、しかも $1$ 回の操作だけで完了するため、最小操作回数が $2$ になることはあり得ない。

制約

すべてのテストデータについて、$T \geqslant 1$、$n \geqslant 1$、$0 \leqslant d_i \leqslant 2$、$1 \leqslant |s_i| = |t_i|$ が保証され、$s_i, t_i$ はともに文字 $\texttt{0}$ と $\texttt{1}$ のみからなる文字列である。

一つのテストケースにおけるすべての初期文字列の長さの総和を $L = \sum_{i=1}^{n} |s_i|$ とし、一つのテストファイル内のすべてのテストケースにおける $L$ の総和を $\sum L$ とすると、$\sum L \leqslant 3\times 10^6$ が保証される。

この問題では適切な小課題の依存関係が設定されている。

• 特殊な性質 A：すべての $1 \leqslant i \leqslant n$ について、$|s_i| \geqslant 50$ が成り立つことが保証される。