有一台专门处理 $\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$。

为了验证你的记忆是否出现偏差，请你判断：是否存在一个规则集 $\mathcal{R}$，使得机器对这 $n$ 组输入的实际输出与你的记忆完全一致？

输入格式

第一行包含一个正整数 $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|$ 为单组测试数据中所有初始串的长度之和，$\sum L$ 为单个测试点内所有测试数据的 $L$ 之和，则保证 $\sum L \leqslant 3\times 10^6$。

本题开启合理的子任务依赖。

• 特殊性质 A：保证对于所有 $1 \leqslant i \leqslant n$，均有 $|s_i| \geqslant 50$。