Ciąg otrzymany przez usunięcie z ciągu zera lub większej liczby elementów nazywamy jego podciągiem. Na przykład aab jest podciągiem $X=\texttt{ababca}$, ale nie jest podciągiem $Y=\texttt{cbabba}$.

Podciąg występujący w obu danych ciągach nazywamy ich wspólnym podciągiem. Na przykład dla powyższych $X$ i $Y$, baa jest wspólnym podciągiem, ale aab nim nie jest.

Dany jest wspólny podciąg $W$ dwóch ciągów $X$ i $Y$. Chcemy ustalić, czy można go rozszerzyć. Mówimy, że $W$ można rozszerzyć, jeśli wstawienie jednego elementu w pewne miejsce $W$ daje dłuższy wspólny podciąg; w przeciwnym razie nie można go rozszerzyć. Na przykład dla powyższych $X$ i $Y$ wspólny podciąg baa można rozszerzyć do baba. Jednak wspólnego podciągu ca nie można już rozszerzyć.

Mając dane dwa ciągi $X$, $Y$ i ich wspólny podciąg $W$, napisz program ustalający, czy $W$ można rozszerzyć.

Ograniczenia

• Jedne dane wejściowe zawierają od $1$ do $100$ przypadków testowych do rozwiązania.
• Sumy $|X|$ oraz $|Y|$ nie przekraczają, każda z osobna, $200\,000$.
• $W$ jest wspólnym podciągiem $X$ i $Y$.
• Ciągi zawierają wyłącznie małe litery alfabetu angielskiego.

Podzadania

1. (14 punktów) $|W| = 1$
2. (17 punktów) Sumy $|X|$ oraz $|Y|$ nie przekraczają, każda z osobna, $300$.
3. (25 punktów) Sumy $|X|$ oraz $|Y|$ nie przekraczają, każda z osobna, $20\,000$.
4. (44 punktów) Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera liczbę przypadków testowych $T$.

Następne $3 \times T$ wierszy zawiera informacje o przypadkach testowych.

Każdy przypadek składa się z trzech wierszy, zawierających odpowiednio ciągi $X$, $Y$ i $W$.

Każdy ciąg jest podany jako kolejne małe litery alfabetu angielskiego bez spacji.

Wyjście

Dla każdego przypadku wypisz informację, czy podciąg można rozszerzyć, po jednym wyniku w wierszu.

Wypisz 1, jeśli można go rozszerzyć, a w przeciwnym razie 0.

Przykład

Wejście 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Wyjście 1

1
0