從一個序列中刪除零個或多個元素後得到的序列，稱為該序列的子序列。 例如，aab 是 $X=\texttt{ababca}$ 的子序列，但不是 $Y=\texttt{cbabba}$ 的子序列。

給定兩個序列，同時出現在兩個序列中的子序列稱為它們的共同子序列。 例如，對於上面的 $X$ 和 $Y$，baa 是它們的共同子序列，但 aab 不是。

給定兩個序列 $X$ 和 $Y$ 的一個共同子序列 $W$，我們想判斷 $W$ 是否可以擴展。 如果在 $W$ 的某個位置插入一個元素，就能得到更長的共同子序列，則稱 $W$ 可擴展；否則稱為不可擴展。 例如，對於上面的 $X$ 和 $Y$，共同子序列 baa 可以擴展為 baba。 但是共同子序列 ca 無法繼續擴展。

給定兩個序列 $X$、$Y$ 以及它們的共同子序列 $W$，請編寫程式判斷 $W$ 是否可擴展。

資料範圍

• 一份輸入中需要處理至少 $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 分) 無額外限制。

輸入格式

第一行給出測試案例數 $T$。

接下來 $3 \times T$ 行給出測試案例的資訊。

每個測試案例由三行組成，依次給出序列 $X$、$Y$、$W$。

每個序列由連續的小寫英文字母給出，不含空格。

輸出格式

對每個測試案例，輸出是否可擴展，每行輸出一個結果。

如果可擴展，輸出 1；否則輸出 0。

範例

輸入格式 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

輸出格式 1

1
0