Every Friday Chef and his N - 1 friends go for a party. At these parties, they play board games. This Friday, they are playing a game named "Boats! Boats! Boats!". In this game players have to transport cookies between Venice and Constantinople. Each player has a personal storage. The players are numbered from 1 to N, Chef is numbered 1. Rules for determining a winner are very difficult, therefore Chef asks you to write a program, which will determine who is a winner. 

There are 6 types of cookies. For each cookie in the storage player gets 1 point. Also player gets additional points if he packs his cookies in some boxes as follows: 

- A box containing 4 different types of cookies fetches 1 additional point.
- A box containing 5 different types of cookies fetches 2 additional points.
- A box containing 6 different types of cookies fetches 4 additional points.

Obviously a cookie can be put into a single box.

For each player, you know the number of cookies in his storage (denoted by c[i]), also the types of cookies in the storage given denoted by type[i][j].

Your task is to determine the winner of this game. Output "tie" if there are two or more players with same maximum score, "chef" if only Chef has a maximum score, winner's index in all other cases.

-----Input-----

The first line of input contains a single integer T denoting the number of test cases. This will be followed by T test cases.
The first line of each test case contains an integer N denoting the number of players.
The second line of each test case contains an integer c[i] denoting the number of cookies in the i-th storage, followed by c[i] space-separated integers type[i][j] which denote the type if j-th cookie in the storage i-th.

-----Output-----
For each test case, output a single line containing the answer as specified in the statement.

-----Constraints and Subtasks-----Subtask #1 : (20 points)  

- 1 ≤ T ≤ 10 
- 1 ≤  N  ≤ 100  
- 1 ≤  c[i]  ≤  100  
- 1 ≤  type[i][j]  ≤  3   
Subtask #2 : (80 points)  

- 1 ≤ T ≤ 10 
- 1 ≤  N  ≤ 100  
- 1 ≤  c[i]  ≤  100  
- 1 ≤  type[i][j]  ≤  6  

-----Example-----
Input:
3
2
6 1 2 3 4 5 6
9 3 3 3 4 4 4 5 5 5
2
5 2 3 4 5 6
7 1 1 2 2 3 3 4
3
4 1 1 2 3
4 1 2 2 3
4 1 2 3 3
Output:
chef
2
tie

-----Explanation-----
Example case 1.
Chef has total 6 cookie, so he gets 6 points for that. Also, he can put all his cookies (as they are all distinct) in a bag of size 6. It will fetch him additional 4 points. So, Chef's total points will be 10.
The second player has 9 cookies, he gets 9 points for that. Other than this, he can't create a bag with either 4, 5 or 6 distinct cookies. So, his final score is 9.
10 > 9 - Chef wins.
Example case 2.
Chef has 5 + 2 (a bag with 5 different cookies) = 7.
The second player has 7 + 1(a bag with 4 different cookies) = 8.
7 < 8 - the second player wins.
Example case 3.
Every player has 4 cookies and can't create any bag of sweets. So, it's a tie.

Difficulty: interview

Starter code:

Solutions:
# cook your code here
for _ in range(eval(input())):
 n=eval(input())
 ind=0
 m=-1
 
 for i in range(n):
  
  l=[int(x) for x in input().split()]
  sc=l[0]
  for j in range(1,len(l)):
   sc+=int(l[j]>=4)+int(l[j]>=5)+2*int(l[j]>=6)
  if sc==m:
   ind=-2
  if sc>m :
   m=sc
   ind=i+1
  
   
 if (ind==-2):
  print("tie")
 elif (ind==1) :
  print("chef")
 else:
  print(ind)

# cook your code here
for _ in range(eval(input())):
 n=eval(input())
 ind=0
 m=0
 
 for i in range(n):
  
  l=[int(x) for x in input().split()]
  sc=l[0]
  for j in range(1,len(l)):
   sc+=int(l[j]>=4)+int(l[j]>=5)+2*int(l[j]>=6)
  if sc==m:
   ind=-2
  if sc>m :
   m=sc
   ind=i+1
  
   
 if (ind==-2):
  print("tie")
 elif (ind==1) :
  print("chef")
 else:
  print(ind)

# cook your code here

T = int(input())

for t in range(T):
 N = int(input())
 C = [0] * N 
 score = [0] * N
 cookies = [ [0] * 7 for _ in range(N)]
 
 for i in range(N):
  
  inpt = input().split(' ')
 
  C[i] = int(inpt[0])
 
  for j in range(C[i]):
   k = int(inpt[j+1])
   cookies[i][k] = cookies[i][k]+1
  
  cookies[i].sort()
  
  six = cookies[i][1]
  five = cookies[i][2]
  four = cookies[i][3]
  
  five = max(0, five-six)
  four = max(0, four-six-five)
  score[i] = C[i] + 4*six + 2*five + 1*four
     
  
 tie = 0 
 maxscore = 0
 maxchef = 0
 for i in range(N):
  if score[i] > maxscore:
   maxscore = score[i]
   tie = 0
   maxchef = i
  elif score[i] == maxscore:
   tie = 1
 
 if tie > 0:
  print("tie")
 elif maxchef == 0:
  print("chef")
 else:
  print(maxchef+1)
  
  
 


t = int(input())
for _ in range(t):
 n = int(input())
 c = []
 for _ in range(0,n):
  c.append(list(map(int,input().split())))
 m = []
 def newset(c):
  for i in set(c[1:]):
   c.remove(i)
  return c
 def check(c):
  s = len(set(c[1:]))
  if s < len(c[1:]):
    check(newset(c))
  if s == 4:
    c[0] += 1
  elif s == 5:
    c[0] += 2
  elif s == 6:
    c[0] += 4
  return c[0]

 for i in c:
  m.append(check(i))
 if m.count(max(m))>1:
  print('tie')
 elif max(m) == m[0]:
  print('chef')
 else:
  print(m.index(max(m))+1)

t=int(input())
for i in range(t):
 n=int(input())
 final=0
 winner=0
 count=0
 winnerPoints=[0]*(n+1)
 for j in range(n):
  c=[int(num) for num in input().strip().split()]
  arr=[0]*7
  for k in range(1,c[0]+1):
   arr[c[k]]+=1
  arr.sort()
  six=arr[1]
  five=arr[2]-six
  four=arr[3]-five-six
  point=(six*4)+(five*2)+(four*1)+c[0]
  if(point>final):
   final=point
   winner=j+1
  winnerPoints[j+1]=point
 for tr in range(1,n+1):
  if(winnerPoints[tr]==final):
   count+=1
 if(count>1):
  print("tie")
 elif(winner==1):
  print("chef")
 else:
  print(str(winner))

t=int(input())
for i in range(t):
 n=int(input())
 final=0
 winner=-1
 winnerPoints=[0]*(n+1)
 for j in range(n):
  c=[int(num) for num in input().strip().split()]
  arr=[0]*6
  for k in range(1,c[0]+1):
   arr[c[k]-1]+=1
  arr.sort()
  six=arr[0]
  five=arr[1]-six
  four=arr[2]-five
  point=(six*4)+(five*2)+(four*1)+c[0]
  if(point>final):
   final=point
   winner=j+1
  winnerPoints[j+1]=point
 count=0
 for t in range(1,n+1):
  if(winnerPoints[t]==final):
   count+=1
 if(count>1):
  print("tie")
 elif(winner==1):
  print("chef")
 else:
  print(str(winner))

from collections import Counter

for _ in range(int(input())):
 N = int(input())
 max_points = [-1, [-1]]
 for player in range(N):
  data = input().split()
  storage_distinct = Counter(data[1:])
  points = int(data[0])
  
  while len(storage_distinct) >= 4:
   if len(storage_distinct) == 4:
    points += 1
   elif len(storage_distinct) == 5:
    points += 2
   elif len(storage_distinct) >= 6:
    points += 4
    
   for i in list(storage_distinct.keys()):
    storage_distinct[i] -= 1
    if storage_distinct[i] == 0:
     del storage_distinct[i]
  
  if points > max_points[0]:
   max_points[0] = points
   max_points[1] = [player]
  elif points == max_points[0]:
   max_points[1].append(player)
   
 if len(max_points[1]) > 1:
  print("tie")
 elif max_points[1][0] == 0:
  print("chef")
 else:
  print(max_points[1][0] + 1)

for _ in range(int(input())):
 N = int(input())
 max_points = [-1, [-1]]
 for player in range(N):
  data = input().split()
  storage_distinct = set(data[1:])
  points = int(data[0])
  if len(storage_distinct) == 4:
   points += 1
  elif len(storage_distinct) == 5:
   points += 2
  elif len(storage_distinct) >= 6:
   points += 4
  
  if points > max_points[0]:
   max_points[0] = points
   max_points[1] = [player]
  elif points == max_points[0]:
   max_points[1].append(player)
   
 if len(max_points[1]) > 1:
  print("tie")
 elif max_points[1][0] == 0:
  print("chef")
 else:
  print(max_points[1][0] + 1)

def max_score(storage):
 """Returns the max score for the given storage array"""
 s = len(storage)
 counts = {}
 for cookie in storage:
  if cookie in counts:
   counts[cookie] += 1
  else:
   counts[cookie] = 1

 # Count boxes of six
 while len(list(counts.keys())) >= 6:
  minimum = min(counts.values())
  s += 4 * minimum
  to_delete = []
  for cookie, count in list(counts.items()):
   counts[cookie] -= minimum
   if counts[cookie] == 0:
    to_delete.append(cookie)
  for key in to_delete:
   counts.pop(key)
 # Count boxes of five
 while len(list(counts.keys())) >= 5:
  minimum = min(counts.values())
  s += 2 * minimum
  to_delete = []
  for cookie, count in list(counts.items()):
   counts[cookie] -= minimum
   if counts[cookie] == 0:
    to_delete.append(cookie)
  for key in to_delete:
   counts.pop(key)
 # Count boxes of four
 while len(list(counts.keys())) >= 4:
  minimum = min(counts.values())
  s += 1 * minimum
  to_delete = []
  for cookie, count in list(counts.items()):
   counts[cookie] -= minimum
   if counts[cookie] == 0:
    to_delete.append(cookie)
  for key in to_delete:
   counts.pop(key)
 return s

T = int(input())
while T > 0:
 N = int(input())
 max_s = -1
 max_idx = 0
 tied = False
 for idx in range(N):
  row = list(map(int, input().split()))
  score = max_score(row[1:])
  if score > max_s:
   max_s = score
   max_idx = idx
   tied = False
  elif score == max_s:
   tied = True
 if tied:
  print('tie')
 elif max_idx == 0:
  print('chef')
 else:
  print(max_idx + 1)
 T -= 1


t=int(input())
for _ in range(t):
 scores=[]
 
 n=int(input())
 for i in range(n):
  items=list(map(int,input().split()))
  p=items[0]
  
  iscore=0
  m=[[] for j in range(p)]
  for k in range(p):
   for l in range(p):
    if items[k+1] not in m[l]:

     m[l].append(items[k+1])
     break
   #print m
  #print m
  for k in range(len(m)):
   if len(m[k])==4:
    iscore+=(4+1)
   elif len(m[k])==5:
    iscore+=(5+2)
   elif len(m[k])==6:
    iscore+=(6+4)
   else:
    iscore+=len(m[k])
  scores.append(iscore)
 #print scores
 f=scores.index(max(scores))
 if scores.count(max(scores))>1:
  print("tie")
 elif f==0:
  print("chef")
 else:
  print(f+1)

for _ in range(int(input())):
 n = int(input())
 a = [list(map(int,input().split())) for _ in range(n)]
 p = list()
 for b in a:
  ans = 0
  d = [0]*6
  for i in b[1:]:
   d[i-1]+=1
  d = sorted(d)
  ans+=d[0]*4
  ans+=(d[1]-d[0])*2
  ans+=(d[2]-d[1])
  ans+=b[0]
  p.append(ans)
 if n==1: print("chef")
 else:
  s = sorted(p)
  if s[n-1]==s[n-2]: print("tie")
  elif p[0]==max(p): print("chef")
  else: print(p.index(max(p))+1)

for _ in range(int(input())):
 n = int(input())
 a = [list(map(int,input().split())) for _ in range(n)]
 p = list()
 for b in a:
  ans = 0
  d = [0]*6
  for i in b[1:]:
   d[i-1]+=1
  d = sorted(d)
  ans+=d[0]*4
  if d[1] - d[0] > 0:
   ans+=(d[1]-d[0])*2
  if d[2] - d[1] - d[0] > 0:
   ans+=(d[2]-d[1]-d[0])
  ans+=b[0]
  p.append(ans) 
 s = sorted(p)
 if s[n-1]==s[n-2]: print("tie")
 elif p[0]==max(p): print("chef")
 else: print(p.index(max(p))+1)

t = int(input())
for _ in range(t):
 n = int(input())
 c = []
 for _ in range(0,n):
  c.append(list(map(int,input().split())))
 s = []
 for i in c:
  s.append(len(set(i[1:])))
 for i in range(len(s)):
  if s[i] == 4:
   s[i] = 1+c[i][0]
  elif s[i] == 5:
   s[i] = 2+c[i][0]
  elif s[i] == 6:
   s[i] = 4+c[i][0]
  else :
   s[i] = c[i][0]
 m = max(s)
 if s.count(m) > 1:
  print('tie')
 else:
  j = s.index(m)
  if j == 0:
   print('chef')
  else :
   print(j+1)