Extending a Common Subsequence

A sequence obtained by deleting zero or more elements from a sequence is called a subsequence of that sequence. For example, aab is a subsequence of $X$ = ababca, but not of $Y$ = cbabba.

A subsequence that appears in both of two sequences is called a common subsequence of the two sequences. For example, for the two sequences $X$ and $Y$ above, baa is a common subsequence of $X$ and $Y$, but aab is not.

Given a common subsequence $W$ of two sequences $X$ and $Y$, we want to decide whether $W$ is extendable. If inserting some element at some position of $W$ produces a longer common subsequence, $W$ is extendable; otherwise $W$ is not extendable. For example, for $X$ and $Y$ above, the common subsequence baa can be extended to baba. The common subsequence ca, however, cannot be extended any further.

Given two sequences $X$, $Y$ and a common subsequence $W$ of the two sequences, write a program that decides whether $W$ is extendable.

The first line contains the number of test cases $T$.

The next $3 \times T$ lines contain the test cases.

Each test case consists of three lines, containing the sequences $X$, $Y$, $W$, one per line.

Each sequence is given as a contiguous string of lowercase English letters with no spaces.

For each test case, print on its own line whether the sequence is extendable.

Print 1 if it is extendable, and 0 otherwise.

• One input file contains between 1 and 100 test cases.
• The sum of $|X|$ and the sum of $|Y|$ are each at most $200\,000$.
• $W$ is a common subsequence of $X$ and $Y$.
• Sequences consist only of lowercase English letters.