Eine Folge, die durch das Löschen von null oder mehr Elementen aus einer Folge entsteht, heißt Teilfolge dieser Folge. Zum Beispiel ist aab eine Teilfolge von $X=\texttt{ababca}$, aber nicht von $Y=\texttt{cbabba}$.

Eine Teilfolge, die in beiden gegebenen Folgen vorkommt, heißt ihre gemeinsame Teilfolge. Zum Beispiel ist für die obigen Folgen $X$ und $Y$ baa eine gemeinsame Teilfolge, aab jedoch nicht.

Gegeben ist eine gemeinsame Teilfolge $W$ zweier Folgen $X$ und $Y$. Wir wollen feststellen, ob sich $W$ erweitern lässt. $W$ heißt erweiterbar, wenn das Einfügen eines Elements an einer Stelle von $W$ eine längere gemeinsame Teilfolge ergibt; andernfalls ist $W$ nicht erweiterbar. Zum Beispiel lässt sich für die obigen $X$ und $Y$ die gemeinsame Teilfolge baa zu baba erweitern. Die gemeinsame Teilfolge ca lässt sich jedoch nicht weiter erweitern.

Gegeben sind zwei Folgen $X$, $Y$ und ihre gemeinsame Teilfolge $W$. Schreibe ein Programm, das feststellt, ob $W$ erweiterbar ist.

Beschränkungen

• Jede Eingabe enthält mindestens $1$ und höchstens $100$ zu lösende Testfälle.
• Die Summen von $|X|$ und $|Y|$ sind jeweils höchstens $200\,000$.
• $W$ ist eine gemeinsame Teilfolge von $X$ und $Y$.
• Die Folgen bestehen nur aus englischen Kleinbuchstaben.

Teilaufgaben

1. (14 Punkte) $|W| = 1$
2. (17 Punkte) Die Summen von $|X|$ und $|Y|$ sind jeweils höchstens $300$.
3. (25 Punkte) Die Summen von $|X|$ und $|Y|$ sind jeweils höchstens $20\,000$.
4. (44 Punkte) Keine zusätzlichen Beschränkungen.

Eingabe

Die erste Zeile enthält die Anzahl der Testfälle $T$.

Die nächsten $3 \times T$ Zeilen enthalten die Informationen zu den Testfällen.

Jeder Testfall besteht aus drei Zeilen, die jeweils die Folgen $X$, $Y$ und $W$ enthalten.

Jede Folge wird als aufeinanderfolgende englische Kleinbuchstaben ohne Leerzeichen angegeben.

Ausgabe

Gib für jeden Testfall an, ob die Teilfolge erweiterbar ist, ein Ergebnis pro Zeile.

Gib 1 aus, wenn sie erweiterbar ist, andernfalls 0.

Beispiele

Eingabe 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Ausgabe 1

1
0