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=\texttt{ababca}$, but not of $Y=\texttt{cbabba}$.

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

Given a common subsequence $W$ of two sequences $X$ and $Y$, we want to determine whether $W$ can be extended. We define $W$ to be extendable if inserting an element at some position in $W$ can produce a longer common subsequence; otherwise, it is not extendable. For example, for $X$ and $Y$ above, the common subsequence baa can be extended to baba. However, the common subsequence ca cannot be extended any further.

Given two sequences $X$, $Y$ and a common subsequence $W$ of them, write a program to determine whether $W$ is extendable.

Constraints

• Each input contains at least $1$ and at most $100$ test cases to solve.
• The sums of $|X|$ and $|Y|$ are each at most $200\,000$.
• $W$ is a common subsequence of $X$ and $Y$.
• The sequences contain only lowercase English letters.

Subtasks

1. (14 points) $|W| = 1$
2. (17 points) The sums of $|X|$ and $|Y|$ are each at most $300$.
3. (25 points) The sums of $|X|$ and $|Y|$ are each at most $20\,000$.
4. (44 points) No additional constraints.

Input

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 $X$, $Y$ and $W$, respectively.

Each sequence is given as consecutive lowercase English letters without spaces.

Output

For each test case, print whether it is extendable, one result per line.

Print 1 if it is extendable, and 0 otherwise.

Examples

Input 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Output 1

1
0