ある列から 0 個以上の要素を削除して得られる列を、その列の部分列といいます。 例えば aab は $X=\texttt{ababca}$ の部分列ですが、$Y=\texttt{cbabba}$ の部分列ではありません。

2 つの列が与えられたとき、両方に現れる部分列を 2 つの列の共通部分列といいます。 例えば、上の $X$ と $Y$ に対して、baa は共通部分列ですが、aab は共通部分列ではありません。

2 つの列 $X$, $Y$ の共通部分列 $W$ が与えられたとき、$W$ を拡張できるか判定したいです。 $W$ のある位置に要素を 1 つ追加して、より長い共通部分列が得られるなら $W$ は拡張可能、そうでなければ拡張不可能と定義します。 例えば、上の $X$ と $Y$ に対して、共通部分列 baa は baba に拡張できます。 しかし、共通部分列 ca はこれ以上拡張できません。

2 つの列 $X$, $Y$ とその共通部分列 $W$ が与えられたとき、$W$ が拡張可能かを判定するプログラムを作成してください。

制約

• 1 つの入力には $1$ 個以上 $100$ 個以下のテストケースがあります。
• $|X|$ の総和と $|Y|$ の総和はそれぞれ $200\,000$ 以下です。
• $W$ は $X$ と $Y$ の共通部分列です。
• 列は英小文字のみからなります。

小課題

1. (14 点) $|W| = 1$
2. (17 点) $|X|$ の総和と $|Y|$ の総和はそれぞれ $300$ 以下です。
3. (25 点) $|X|$ の総和と $|Y|$ の総和はそれぞれ $20\,000$ 以下です。
4. (44 点) 追加の制約はありません。

入力

1 行目にテストケース数 $T$ が与えられます。

続く $3 \times T$ 行にテストケースの情報が与えられます。

各テストケースは 3 行からなり、各行に列 $X$, $Y$, $W$ がそれぞれ与えられます。

各列は空白を含まない連続した英小文字で与えられます。

出力

各テストケースについて、拡張可能かを 1 行に 1 つずつ出力してください。

拡張可能なら 1、不可能なら 0 を出力してください。

入出力例

入力 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

出力 1

1
0