Une séquence obtenue en supprimant zéro ou plusieurs éléments d’une séquence est appelée une sous-séquence de celle-ci. Par exemple, aab est une sous-séquence de $X=\texttt{ababca}$, mais pas de $Y=\texttt{cbabba}$.

Une sous-séquence apparaissant dans les deux séquences données est appelée leur sous-séquence commune. Par exemple, pour les séquences $X$ et $Y$ ci-dessus, baa est une sous-séquence commune, mais aab ne l’est pas.

Étant donnée une sous-séquence commune $W$ de deux séquences $X$ et $Y$, nous voulons déterminer si $W$ peut être étendue. On dit que $W$ est extensible si l’insertion d’un élément à une certaine position de $W$ produit une sous-séquence commune plus longue ; sinon, elle n’est pas extensible. Par exemple, pour les $X$ et $Y$ ci-dessus, la sous-séquence commune baa peut être étendue en baba. En revanche, la sous-séquence commune ca ne peut plus être étendue.

Étant données deux séquences $X$, $Y$ et une sous-séquence commune $W$ de celles-ci, écrivez un programme déterminant si $W$ est extensible.

Contraintes

• Chaque entrée contient au moins $1$ et au plus $100$ cas de test à résoudre.
• Les sommes de $|X|$ et de $|Y|$ sont chacune au plus égales à $200\,000$.
• $W$ est une sous-séquence commune de $X$ et $Y$.
• Les séquences ne contiennent que des lettres minuscules anglaises.

Sous-tâches

1. (14 points) $|W| = 1$
2. (17 points) Les sommes de $|X|$ et de $|Y|$ sont chacune au plus égales à $300$.
3. (25 points) Les sommes de $|X|$ et de $|Y|$ sont chacune au plus égales à $20\,000$.
4. (44 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient le nombre de cas de test $T$.

Les $3 \times T$ lignes suivantes contiennent les informations des cas de test.

Chaque cas comprend trois lignes contenant respectivement les séquences $X$, $Y$ et $W$.

Chaque séquence est donnée sous forme de lettres minuscules anglaises consécutives, sans espaces.

Sortie

Pour chaque cas, affichez si elle est extensible, avec un résultat par ligne.

Affichez 1 si elle est extensible, et 0 sinon.

Exemples

Entrée 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Sortie 1

1
0