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.

Input
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 wi, the i-th word in the dictionary.

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

Example

Input:
3
codechef
2
code
chef
foo
1
bar
mississippi
4
ssissi
mippi
mi
ppi

Output:
Tracy
Tracy
Teddy


Constraints

1 <= T <= 5
1 <= N <= 30
1 <= |S| <= 30
1 <= |wi| <= 30
S and wi contain only characters 'a'-'z'
__author__ = 'robert'
from collections import defaultdict
import sys

def solve(cache, between, i, j):
    if (i, j) in cache:
        return cache[(i, j)]
    if not between[(i, j)]:
        return 0
    if len(between[(i, j)]) == 1:
        return 1
    grundy_numbers = set()
    for word in between[(i, j)]:
        start, end = word
        grundy_numbers.add(
            solve(cache, between, i, start) ^ solve(cache, between, end, j)
        )
    mex = 0
    while mex in grundy_numbers:
        mex += 1
    cache[(i, j)] = mex
    return mex



def run():
    input_ = (i.strip() for i in sys.stdin)
    test_cases = int(next(input_))
    for case in range(test_cases):
        s = next(input_)
        n = int(next(input_))
        words = [next(input_) for i in range(n)]
        word_locations = []
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in words:
                    word_locations.append((i, j))
        between = defaultdict(list)
        for word in word_locations:
            start, end = word
            for i in range(start + 1):
                for j in range(end, len(s) + 1):
                    between[(i, j)].append(word)
        cache = {}
        print "Teddy" if solve(cache, between, 0, len(s)) else "Tracy"

run()