Имеется машина преобразования строк, специально предназначенная для обработки $\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{01}$ строки $\texttt{001}$ на $\texttt{10}$, можно за $1$ шаг получить $\texttt{010}$.
  • Для $3$-го запроса, поскольку $\texttt{001}$ и $\texttt{100}$ различаются и на $1$-й, и на $3$-й позициях, с помощью одного лишь правила длины $2$ невозможно выполнить преобразование за $1$ шаг; однако можно сначала заменить суффикс $\texttt{01}$ начальной строки $\texttt{001}$ на $\texttt{10}$, получив промежуточную строку $\texttt{010}$, а затем заменить префикс $\texttt{01}$ промежуточной строки $\texttt{010}$ на $\texttt{10}$, получив целевую строку $\texttt{100}$, поэтому минимальное количество шагов операций равно $2$.
• $2$-й набор входных данных: чтобы за $1$ шаг преобразовать $\texttt{10}$ в $\texttt{01}$, множество правил $\mathcal{R}$ обязательно должно содержать правило $(\texttt{10}, \texttt{01})$. Однако при наличии этого правила во $2$-м запросе достаточно заменить префикс $\texttt{10}$ строки $\texttt{100}$ на $\texttt{01}$, чтобы получить $\texttt{010}$ за $1$ шаг, что противоречит значению $d_2 = 2$ в вашей памяти.
• $3$-й набор входных данных: все строки в процессе преобразования должны быть $\texttt{01}$-строками одинаковой длины. Существует всего две $\texttt{01}$-строки длины $1$: $\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$.