Lucy and her friends are heading to the bar to play darts, the forever fierce battle between drunk people to show who’s the best at throwing some sharpened darts into a board. Seems like a lot of fun.

As crazy as it may appear, Lucy and her friends have mad skills when playing darts, as they may all win flawlessly (and this is not fun at all), they have decided to challenge themselves a little bit with some luck. They will draw from a bowl N numbers ranging from 1 to 60 and then they will try to reach 0 at a standard game of 301.

When playing 301, you start your score at 301 points, for each turn you have three throws, for each throw you will substract the value thrown to the current value you have, if, for some reason you exceed the score you must get to be at 0 points, nothing you’ve done at that turn will be taken into count. If you get to 0 at some point of the game, you win. After your turns ends, the other player’s start its throws

For instance, if you have 32 points left on your board to get to 0 and you throw 2 darts at 16, you win, but if you throw a dart at 17 and 16 (thus earning 33 points), you reset yourself to 32 again and your turn is immediately over, and if you score something like 8, 8 and 12 (earning 28 points), next turn you will have to make 4 points to win.

Lucy and her friends want to know who’s going to be the expected winner at the darts game, because if that person does not win, he or she will pay all the beers!

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

For each test case you will have an integer N and K representing, respectively, the number of players and the number of scores they will have to make on the board. Then, N lines will follow with K integers separated by a single space denoting the score Kj that a player Ni must make on that turn.

For simplicity, we will assume that they can score any number between 1 and 60 (inclusive) regardless of the board points configuration and that after they throw K darts, they will stop throwing and, if no player has won yet, declare a tie.

Output

For each case you must print the number (1-index based) of the player that is expected to win the standard game of 301 respecting the order of the input, if there is no player that wins the game after throwing all of its darts, print ”TIE” (without quotes)

Example

Input:
3
3 4
60 60 60 58
60 60 60 60
60 59 58 57
3 9
60 60 60 60 40 10 10 1 60
10 20 30 40 50 60 60 60 60
60 60 60 60 60 1 60 60 60
3 9
60 60 60 60 50 10 5 1 50
60 60 60 60 40 10 5 1 5
60 60 60 60 60 60 60 60 60

Output:
TIE
3
2

Constraints

• 1 ≤ N ≤ 100

• 1 ≤ K ≤ 301

• 1 ≤ Ki ≤ 60

Explanation of the third case: at the end of the first round, player 1, 2 and 3 scored 180 points, at the second round, player 1 scored 120 (1 points left), player 2 scored 110 (11 point left) and player 3 scored 180 points (131 left as it got busted), by the next round, player 1 bust out with one throw at 5 points and then, player 2 wins by scoring in three throws 5,1,5 (earning 11 points).