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'

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys

def mex(S, W, C, start, end):
	key = (start, end)
	try:
		return C[key]
	except KeyError:
		pass
	A = set()
	for s in range(start, end):
		for e in range(start + 1, end + 1):
			if S[s:e] not in W:
				continue
			A.add(mex(S, W, C, start, s) ^ mex(S, W, C, e, end))
	a = 0
	while a in A:
		a += 1
	C[key] = a
	return a
a = sys.stdin
T = int(a.readline())
for t in range(T):
	S = a.readline().strip()
	N = int(a.readline())
	W = set([a.readline().strip() for n in range(N)])
	print('Teddy' if mex(S, W, {}, 0, len(S)) else 'Tracy')


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')


D = {}

def g(s):
	if s in D:
		return D[s]
	vals = set()
	l = len(s)
	for i in range(l):
		for j in range(1, l + 1 - i):
			sub = s[i:i + j]
			if sub in DIC:
				vals.add(g(s[:i]) ^ g(s[i + j:]))
	i = 0
	while 1:
		if not i in vals:
			break
		i += 1
	D[s] = i
	return D[s]
T = int(input(''))
for t in range(T):
	s = input('')
	d_len = int(input(''))
	DIC = set()
	for i in range(d_len):
		DIC.add(input(''))
	D = {}
	print('Teddy' if g(s) else 'Tracy')