There is a string transformation machine that specifically processes $\texttt{01}$ strings, with a built-in finite set of rules $\mathcal{R}$. Each rule is of the form $(u, v)$, where $u, v$ are non-empty $\texttt{01}$ strings of equal length, indicating that in one step of operation, you can choose a substring $u$ of the current string and replace it with $v$. Each time a pair of non-empty $\texttt{01}$ strings $(s, t)$ of equal length is fed into the machine, the machine outputs the minimum number of operation steps required to transform $s$ into $t$, or reports that there is no solution.

You recall that you once fed $n$ pairs of non-empty $\texttt{01}$ strings of equal length $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ into this machine. Coincidentally, in your memory, every query not only had a solution, but also satisfied that the minimum number of operation steps was $d_i \leqslant 2$.

To verify whether your memory is flawed, please determine: does there exist a rule set $\mathcal{R}$ such that the machine's actual outputs for these $n$ inputs are completely consistent with your memory?

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $n$, representing the number of query records. In the next $n$ lines, the $i$-th line contains two non-empty $\texttt{01}$ strings $s_i, t_i$ of equal length and an integer $d_i$ ($0 \leqslant d_i \leqslant 2$), representing the initial string, the target string, and the minimum number of operation steps given by the machine for the $i$-th input, respectively.

Output

For each test case, output a single string on a line. If there exists a rule set $\mathcal{R}$ satisfying the conditions, output YES; otherwise, output NO.

You may output YES and NO in any case; for example, yes, Yes, or YES will all be regarded as the same answer.

Examples

Input 1

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

Output 1

YES
NO
NO

Note

• Test case $1$: We can construct a set containing only one rule, $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • For the $1$-st query, $s_1 = t_1 = \texttt{010}$, so the transformation is completed without any operations, and the minimum number of operation steps is $0$.
  • For the $2$-nd query, replacing the suffix $\texttt{01}$ of $\texttt{001}$ with $\texttt{10}$ yields $\texttt{010}$ in $1$ step.
  • For the $3$-rd query, since $\texttt{001}$ and $\texttt{100}$ differ at both the $1$-st and the $3$-rd positions, a rule of length $2$ alone cannot complete the transformation in $1$ step; however, we can first replace the suffix $\texttt{01}$ of the initial string $\texttt{001}$ with $\texttt{10}$ to get the intermediate string $\texttt{010}$, and then replace the prefix $\texttt{01}$ of the intermediate string $\texttt{010}$ with $\texttt{10}$ to get the target string $\texttt{100}$, so the minimum number of operation steps is $2$.
• Test case $2$: In order to transform $\texttt{10}$ into $\texttt{01}$ in $1$ step, the rule set $\mathcal{R}$ must contain the rule $(\texttt{10}, \texttt{01})$. However, once this rule is included, the $2$-nd query only needs to replace the prefix $\texttt{10}$ of $\texttt{100}$ with $\texttt{01}$ to obtain $\texttt{010}$ in $1$ step, which contradicts $d_2 = 2$ in your memory.
• Test case $3$: All strings during the transformation process must be $\texttt{01}$ strings of equal length. There are only two $\texttt{01}$ strings of length $1$, namely $\texttt{0}$ and $\texttt{1}$. If $\texttt{0}$ can be transformed into $\texttt{1}$, then the rule $(\texttt{0}, \texttt{1})$ must exist and the transformation can be completed in just $1$ step, so it is impossible for the minimum number of steps required to be $2$.

Constraints

For all test data, it is guaranteed that $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, and both $s_i, t_i$ are strings consisting only of the characters $\texttt{0}$ and $\texttt{1}$.

Let $L = \sum_{i=1}^{n} |s_i|$ be the sum of lengths of all initial strings in a single test case, and $\sum L$ be the sum of $L$ over all test cases in a single test file; it is guaranteed that $\sum L \leqslant 3\times 10^6$.

Reasonable subtask dependencies are enabled for this problem.

• Special Property A: It is guaranteed that for all $1 \leqslant i \leqslant n$, $|s_i| \geqslant 50$ holds.