Impartial Strings

Time limit4sMemory limit1024 MB

Summary

For each case, decide whether a finite automaton can generate exactly the strings where S and T occur equally often as substrings.

Level: Hard9 of 10
Topics: String matching, Math
Solved: No attempts yet

Problem

Alice builds machines that generate strings. A machine has $N$ states, numbered from 1 to $N$ , and directed edges between them. Each edge is labelled with a character from a fixed set. Some states are final. The machine starts at state 1, follows a path that ends at a final state, and concatenates the edge labels along the path in order to produce a string. The path may visit the same state or traverse the same edge more than once. It may pass through final states before it ends at one. Self loops are allowed, and two or more edges between the same pair of states with the same label are also allowed.

Bob has a favorite string $S$ , and Carol has a favorite string $T$ . Alice wants to know whether she can build a machine that generates exactly the strings that contain the same number of occurrences of $S$ and $T$ as substrings. The machine must generate every such string and no other string. Occurrences may overlap. For example, banana contains two occurrences of ana.

Figure H.1 shows a machine for the first test case in the sample input. Square states are final.

Input

The first line contains a single positive integer $K$ ( $1\leq K \leq 50$ ), the number of test cases. Each of the next $K$ lines contains three strings $A$ , $S$ , and $T$ . $A$ is the fixed set of characters used in the machine. Its characters are distinct lowercase English letters. $S$ is Bob's string, and $T$ is Carol's string. The lengths satisfy $1\leq |S|,|T|\leq 500$ . Every distinct character in $S$ and $T$ appears in $A$ .

Output

For each test case, print one line containing 1 if Alice can build such a machine, and 0 otherwise.

Examples1

Example 1

Input

3
ab ab ba
abc ab ba
cz cczz zzcc

Expected output

1
0
0