Є машина перетворення рядків, яка спеціально обробляє $\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$.