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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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)


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


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):
	s = len(storage)
	counts = {}
	for cookie in storage:
		if cookie in counts:
			counts[cookie] += 1
		else:
			counts[cookie] = 1
	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)
	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)
	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
		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)
	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)


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)