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'
#!/usr/bin/env python

def memo(func):
    cache = {}
    def f(*args):
        if args in cache:
            return cache[args]
        r = func(*args)
        cache[args] = r
        return r
    return f

def doit():
    s = input().strip()
    words = set([input().strip() for x in range(eval(input()))])
    @memo
    def g(start, end):
        num = set([])
        if start >= end: return 0
        for w in words:
            x = start
            while x + len(w) <= end:
                r = s.find(w, x, end)
                if r == -1:
                    break
                num.add(g(start, r) ^ g(r + len(w), end))
                x = r + 1
        x = 0
        while x in num:
            x += 1
        return x
    return g(0, len(s)) > 0

n = eval(input())
for x in range(n):
    if doit():
        print('Teddy')
    else:
        print('Tracy')

#!/usr/bin/env python

def memo(func):
    cache = {}
    def f(*args):
        if args in cache:
            return cache[args]
        r = func(*args)
        cache[args] = r
        return r
    return f

def doit():
    s = input().strip()
    words = set([input().strip() for x in range(eval(input()))])
    @memo
    def g(start, end):
        num = set([])
        if start >= end: return 0
        for w in words:
            x = start
            while x + len(w) <= end:
                r = s.find(w, x, end)
                if r == -1:
                    break
                num.add(g(start, r) ^ g(r + len(w), end))
                x = r + 1
        x = 0
        while x in num:
            x += 1
        return x
    return g(0, len(s)) > 0

n = eval(input())
for x in range(n):
    if doit():
        print('Teddy')
    else:
        print('Tracy')
