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'

Difficulty: interview

Starter code:

Solutions:
import sys

def mex(S,W,C,start,end):
    """Returns Nim-number of S[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
#a=open('astrgame.txt','r')
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')
    


#!/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([])
        x = start
        while x <= end:
            y = x
            while y <= end:
                if s[x:y+1] in words:
                    num.add(g(start, x-1) ^ g(y+1, end))
                y += 1
            x += 1
        x = 0
        while x in num:
            x += 1
        return x
    return g(0, len(s) - 1) > 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")