A - A String Game

Time limit: 1 s
Memory limit: 128 MiB
Languages: C, C++, Java, JavaScript, ... (details)

Teddy and Tracy like to play a game based on strings. The game is as follows. Initially, Tracy writes a long random string on a whiteboard. Then, each player starting with Teddy makes turn alternately. Each turn, the player must erase a contiguous substring that exists in the dictionary. The dictionary consists of $N$ words.

Of course, the player that can't erase any substring in his turn loses the game, and the other player is declared the winner.

Note that after a substring $R$ is erased, the remaining substring becomes separated, i.e. they cannot erase a word that occurs partially to the left of $R$ and partially to the right of $R$.

Determine the winner of the game, assuming that both players play optimally.


The first line contains a single integer $T$, the number of test cases. $T$ test cases follow. The first line of each testcase contains a string $S$, the string Tracy writes on the whiteboard. The next line contains a single integer $N$. $N$ lines follow. The $i$-th line contains a single string $w_i$, the $i$-th word in the dictionary.

$1 \leq T \leq 5$
$1 \leq N \leq 30$
$1 \leq |S| \leq 30$
$1 \leq |w_i| \leq 30$

$S$ and $w_i$ contain only characters $\texttt{`a'} - \texttt{`z'}$.


For each test case, output a single line containing the name of the winner of the game.

Sample test(s)

3 codechef 2 code chef foo 1 bar mississippi 4 ssissi mippi mi ppi
Tracy Tracy Teddy