Problem H
Impartial Strings

Alice builds machines that generates strings. Alice’s machines each consist of $N$ states, numbered from $1$ to $N$, and a set of directed edges between these states, each labelled with a character from a fixed set. A subset of the states are “final” states. The machine generates strings by starting at state $1$, following a path that terminates at a final state, and concatenating the characters of the edge labels together in the order that the edges are traversed. The path is allowed to visit the same state more than once and can traverse the same edge more than once. The path can pass through final states before eventually terminating at a final state. Self loops are allowed and having two or more edges to and/or from the same state labelled with the same letter is also allowed.

Bob has a favorite string $S$. Carol has a favorite string $T$. Alice wonders if she can build a machine that can generate exactly the strings that have an equal number of occurrences of $S$ and $T$ as substrings. That is, the machine should generate every string that has an equal number of occurrences of $S$ and $T$ as substrings and it should not generate any strings that do not satisfy this property. Occurrences may overlap. For example, the string banana has two occurrences of the substring ana. Help Alice determine if it is possible to complete the task for Bob and Carol’s favorite strings.

Figure 1: Example machine for the first case in the sample input.

Figure 1 gives an example machine for the first case in the sample input. The square states represent the final states.

Input

The first line of input contains a single positive integer $K$ $(1\leq K \leq 50)$, the number of test cases. This is followed by $K$ lines each containing three strings $A$, $S$, $T$. The first string, $A$, is the fixed set of characters used in the machine. The characters in $A$ are distinct lowercase english letters. The second string, $S$, is Bob’s favorite string. The third string, $T$, is Carol’s favorite string. The lengths of $S$ and $T$ satisfy $1\leq |S|,|T|\leq 500$. It is guaranteed that the distinct characters in $S$ and $T$ are a subset of those in $A$.

Output

Output one line for each test case. Output $1$ if Alice can build a machine as described. Otherwise, output $0$.

3
ab ab ba
abc ab ba
cz cczz zzcc

1
0
0