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.

```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 = 'def max_score(storage):\n """Returns the max score for the given storage array"""\n s = len(storage)\n counts = {}\n for cookie in storage:\n  if cookie in counts:\n   counts[cookie] += 1\n  else:\n   counts[cookie] = 1\n\n # Count boxes of six\n while len(list(counts.keys())) >= 6:\n  minimum = min(counts.values())\n  s += 4 * minimum\n  to_delete = []\n  for cookie, count in list(counts.items()):\n   counts[cookie] -= minimum\n   if counts[cookie] == 0:\n    to_delete.append(cookie)\n  for key in to_delete:\n   counts.pop(key)\n # Count boxes of five\n while len(list(counts.keys())) >= 5:\n  minimum = min(counts.values())\n  s += 2 * minimum\n  to_delete = []\n  for cookie, count in list(counts.items()):\n   counts[cookie] -= minimum\n   if counts[cookie] == 0:\n    to_delete.append(cookie)\n  for key in to_delete:\n   counts.pop(key)\n # Count boxes of four\n while len(list(counts.keys())) >= 4:\n  minimum = min(counts.values())\n  s += 1 * minimum\n  to_delete = []\n  for cookie, count in list(counts.items()):\n   counts[cookie] -= minimum\n   if counts[cookie] == 0:\n    to_delete.append(cookie)\n  for key in to_delete:\n   counts.pop(key)\n return s\n\nT = int(input())\nwhile T > 0:\n N = int(input())\n max_s = -1\n max_idx = 0\n tied = False\n for idx in range(N):\n  row = list(map(int, input().split()))\n  score = max_score(row[1:])\n  if score > max_s:\n   max_s = score\n   max_idx = idx\n   tied = False\n  elif score == max_s:\n   tied = True\n if tied:\n  print(\'tie\')\n elif max_idx == 0:\n  print(\'chef\')\n else:\n  print(max_idx + 1)\n T -= 1\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13317