Una secuencia obtenida eliminando cero o más elementos de una secuencia se llama subsecuencia de esta. Por ejemplo, aab es una subsecuencia de $X=\texttt{ababca}$, pero no de $Y=\texttt{cbabba}$.

Una subsecuencia que aparece en las dos secuencias dadas se llama subsecuencia común de ambas. Por ejemplo, para las secuencias $X$ e $Y$ anteriores, baa es una subsecuencia común, pero aab no lo es.

Dada una subsecuencia común $W$ de dos secuencias $X$ e $Y$, queremos determinar si $W$ puede ampliarse. Decimos que $W$ puede ampliarse si insertar un elemento en alguna posición de $W$ produce una subsecuencia común más larga; en caso contrario, no puede ampliarse. Por ejemplo, para las $X$ e $Y$ anteriores, la subsecuencia común baa puede ampliarse a baba. Sin embargo, la subsecuencia común ca no puede ampliarse más.

Dadas dos secuencias $X$, $Y$ y una subsecuencia común $W$ de ambas, escribe un programa que determine si $W$ puede ampliarse.

Restricciones

• Cada entrada contiene entre $1$ y $100$ casos de prueba que deben resolverse.
• Las sumas de $|X|$ y de $|Y|$ son, cada una, como máximo $200\,000$.
• $W$ es una subsecuencia común de $X$ e $Y$.
• Las secuencias solo contienen letras minúsculas inglesas.

Subtareas

1. (14 puntos) $|W| = 1$
2. (17 puntos) Las sumas de $|X|$ y de $|Y|$ son, cada una, como máximo $300$.
3. (25 puntos) Las sumas de $|X|$ y de $|Y|$ son, cada una, como máximo $20\,000$.
4. (44 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene el número de casos de prueba $T$.

Las siguientes $3 \times T$ líneas contienen la información de los casos de prueba.

Cada caso consta de tres líneas que contienen las secuencias $X$, $Y$ y $W$, respectivamente.

Cada secuencia se da mediante letras minúsculas inglesas consecutivas, sin espacios.

Salida

Para cada caso, imprime si se puede ampliar, con un resultado por línea.

Imprime 1 si se puede ampliar y 0 en caso contrario.

Ejemplos

Entrada 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Salida 1

1
0