Existe una máquina de transformación de cadenas que procesa específicamente cadenas $\texttt{01}$, la cual tiene preconfigurado internamente un conjunto finito de reglas $\mathcal{R}$. Cada regla tiene la forma $(u, v)$, donde $u, v$ son cadenas $\texttt{01}$ no vacías de igual longitud, lo que indica que en un paso de operación se puede elegir una subcadena $u$ de la cadena actual y reemplazarla por $v$. Cada vez que se introduce en la máquina un par de cadenas $\texttt{01}$ no vacías de igual longitud $(s, t)$, la máquina devuelve el número mínimo de pasos de operación necesarios para transformar $s$ en $t$, o informa que no hay solución.

Recuerdas haber introducido alguna vez en esta máquina $n$ pares de cadenas $\texttt{01}$ no vacías de igual longitud $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$. Casualmente, según tus recuerdos, cada consulta no solo tenía solución, sino que además cumplía que el número mínimo de pasos de operación era $d_i \leqslant 2$.

Para verificar si tu memoria tiene algún fallo, determina: ¿existe un conjunto de reglas $\mathcal{R}$ tal que las salidas reales de la máquina para estas $n$ entradas coincidan exactamente con tus recuerdos?

Entrada

La primera línea contiene un entero positivo $T$, que representa el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero positivo $n$, que representa la cantidad de registros de consultas. En las siguientes $n$ líneas, la $i$-ésima línea contiene dos cadenas $\texttt{01}$ no vacías de igual longitud $s_i, t_i$ y un entero $d_i$ ($0 \leqslant d_i \leqslant 2$), que representan respectivamente la cadena inicial, la cadena objetivo y el número mínimo de pasos de operación dado por la máquina en la $i$-ésima entrada.

Salida

Para cada caso de prueba, imprime una línea con una cadena. Si existe un conjunto de reglas $\mathcal{R}$ que cumpla las condiciones, imprime YES; de lo contrario, imprime NO.

Puedes imprimir YES y NO usando cualquier combinación de mayúsculas y minúsculas; por ejemplo, yes, Yes o YES se considerarán la misma respuesta.

Ejemplos

Entrada 1

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

Salida 1

YES
NO
NO

Nota

• Caso de prueba $1$: Se puede construir un conjunto que contenga una sola regla, $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • Para la $1$-ra consulta, $s_1 = t_1 = \texttt{010}$, no se necesita ninguna operación para completar la transformación y el número mínimo de pasos de operación es $0$.
  • Para la $2$-da consulta, al reemplazar el sufijo $\texttt{01}$ de $\texttt{001}$ por $\texttt{10}$, se obtiene $\texttt{010}$ en $1$ paso.
  • Para la $3$-ra consulta, dado que $\texttt{001}$ y $\texttt{100}$ difieren tanto en la $1$-ra como en la $3$-ra posición, con solo reglas de longitud $2$ no es posible completar la transformación en $1$ paso; sin embargo, primero se puede reemplazar el sufijo $\texttt{01}$ de la cadena inicial $\texttt{001}$ por $\texttt{10}$ para obtener la cadena intermedia $\texttt{010}$, y luego reemplazar el prefijo $\texttt{01}$ de la cadena intermedia $\texttt{010}$ por $\texttt{10}$ para obtener la cadena objetivo $\texttt{100}$, por lo que el número mínimo de pasos de operación es $2$.
• Caso de prueba $2$: Para transformar $\texttt{10}$ en $\texttt{01}$ en $1$ paso, el conjunto de reglas $\mathcal{R}$ debe contener la regla $(\texttt{10}, \texttt{01})$. Sin embargo, una vez incluida dicha regla, en la $2$-da consulta basta con reemplazar el prefijo $\texttt{10}$ de $\texttt{100}$ por $\texttt{01}$ para obtener $\texttt{010}$ en $1$ paso, lo cual contradice el $d_2 = 2$ de tus recuerdos.
• Caso de prueba $3$: Todas las cadenas durante el proceso de transformación deben ser cadenas $\texttt{01}$ de igual longitud. Solo existen dos cadenas $\texttt{01}$ de longitud $1$, que son $\texttt{0}$ y $\texttt{1}$. Si se puede transformar $\texttt{0}$ en $\texttt{1}$, entonces necesariamente existe la regla $(\texttt{0}, \texttt{1})$ y basta $1$ paso para completarlo, por lo que es imposible que se necesiten como mínimo $2$ pasos.

Restricciones

Para todos los datos de prueba, se garantiza que $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, y que tanto $s_i, t_i$ son cadenas que contienen únicamente los caracteres $\texttt{0}$ y $\texttt{1}$.

Sea $L = \sum_{i=1}^{n} |s_i|$ la suma de las longitudes de todas las cadenas iniciales en un solo caso de prueba, y $\sum L$ la suma de $L$ de todos los casos de prueba dentro de un mismo archivo de prueba; se garantiza que $\sum L \leqslant 3\times 10^6$.

Este problema tiene activadas dependencias razonables entre subtareas.

• Propiedad especial A: Se garantiza que para todo $1 \leqslant i \leqslant n$, se cumple $|s_i| \geqslant 50$.