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'

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\n\ndef mex(S,W,C,start,end):\n    """Returns Nim-number of S[start:end]"""\n    key=(start,end)\n    try:\n        return C[key]\n    except KeyError:\n        pass\n    A=set()\n    for s in range(start,end):\n        for e in range(start+1,end+1):\n            if S[s:e] not in W: continue\n            A.add(mex(S,W,C,start,s)^mex(S,W,C,e,end))\n    a=0\n    while a in A: a+=1\n    C[key]=a\n    return a\n    \n\na=sys.stdin\n#a=open(\'astrgame.txt\',\'r\')\nT=int(a.readline())\nfor t in range(T):\n    S=a.readline().strip()\n    N=int(a.readline())\n    W=set([a.readline().strip() for n in range(N)])\n    print(\'Teddy\' if mex(S,W,{},0,len(S)) else \'Tracy\')\n    \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13377