题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

对一个序列来说，删除其中的若干个元素（可能为 0 个）后所得到的新序列被称为它的“子序列”。例如，字符串 aab 是 $X =$ ababca 的子序列，但不是 $Y =$ cbabba 的子序列。

若两个序列中都包含某个子序列 $W$，则 $W$ 称为这两个序列的“公共子序列”。例如，在上述的 $X$ 和 $Y$ 中，baa 是它们的公共子序列，但 aab 不是。

现在，给定两个字符串 $X$ 和 $Y$，以及它们的一个公共子序列 $W$，我们想判断 $W$ 是否可以扩展。定义如下：

• 若可以在 $W$ 的某个位置插入一个字符，使其仍然为 $X$ 和 $Y$ 的公共子序列，则称 $W$ 是“可扩展”的；
• 否则，称其为“不可扩展”的。

例如，若 $W =$ baa，可以扩展为 baba，所以 $W$ 是可扩展的。但若 $W =$ ca，则无法再扩展。

请编写程序判断给定的 $W$ 是否可扩展。

输入格式

第一行输入一个整数 $T$，表示测试用例数量。
接下来的 $3 \times T$ 行中，每 3 行描述一个测试用例，依次为：
第 1 行：字符串 $X$
第 2 行：字符串 $Y$
第 3 行：字符串 $W$

输出格式

对每个测试用例，输出一行：若 $W$ 可扩展，输出 1；否则输出 0。

2
ababca
cbabba
baa
aaabbbccc
caacbbc
ccc

1
0

提示

约束条件

• 每组输入中包含 1 到 100 个测试用例
• 所有测试用例中，$|X|$ 的总长度不超过 200,000，$|Y|$ 的总长度也不超过 200,000
• $W$ 是 $X$ 和 $Y$ 的公共子序列
• 所有序列仅包含小写英文字母

子任务

1.（14 分）$|W| = 1$
2.（17 分）$|X|$ 和 $|Y|$ 的总长度均不超过 300
3.（25 分）$|X|$ 和 $|Y|$ 的总长度均不超过 20,000
4.（44 分）无附加约束条件