Running for Gold solution codeforces

Running for Gold solution codeforces



The Olympic Games have just started and Federico is eager to watch the marathon race.

There will be nn athletes, numbered from 11 to nn, competing in the marathon, and all of them have taken part in 55 important marathons, numbered from 11 to 55, in the past. For each 1in1≤i≤n and 1j51≤j≤5, Federico remembers that athlete ii ranked ri,jri,j-th in marathon jj (e.g., r2,4=3r2,4=3 means that athlete 22 was third in marathon 44).

Federico considers athlete xx superior to athlete yy if athlete xx ranked better than athlete yy in at least 33 past marathons, i.e., rx,j<ry,jrx,j<ry,j for at least 33 distinct values of jj.

Federico believes that an athlete is likely to get the gold medal at the Olympics if he is superior to all other athletes.

Find any athlete who is likely to get the gold medal (that is, an athlete who is superior to all other athletes), or determine that there is no such athlete.

Input

The first line contains a single integer tt (1t10001≤t≤1000) — the number of test cases. Then tt test cases follow.

The first line of each test case contains a single integer nn (1n500001≤n≤50000) — the number of athletes.

Then nn lines follow, each describing the ranking positions of one athlete.

The ii-th of these lines contains the 55 integers ri,1,ri,2,ri,3,ri,4,ri,5ri,1,ri,2,ri,3,ri,4,ri,5 (1ri,j500001≤ri,j≤50000) — the ranking positions of athlete ii in the past 55 marathons. It is guaranteed that, in each of the 55 past marathons, the nn athletes have distinct ranking positions, i.e., for each 1j51≤j≤5, the nn values r1,j,r2,j,,rn,jr1,j,r2,j,…,rn,j are distinct.

It is guaranteed that the sum of nn over all test cases does not exceed 5000050000.

Output

For each test case, print a single integer — the number of an athlete who is likely to get the gold medal (that is, an athlete who is superior to all other athletes). If there are no such athletes, print 1−1. If there is more than such one athlete, print any of them.

Example

input

Copy
4
1
50000 1 50000 50000 50000
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
6
9 5 3 7 1
7 4 1 6 8
5 6 7 3 2
6 7 8 8 6
4 2 2 4 5
8 3 6 9 4

output

Copy
1
-1
1
5
Note

Explanation of the first test case: There is only one athlete, therefore he is superior to everyone else (since there is no one else), and thus he is likely to get the gold medal.

Explanation of the second test case: There are n=3n=3 athletes.

  • Athlete 11 is superior to athlete 22. Indeed athlete 11 ranks better than athlete 22 in the marathons 1122 and 33.
  • Athlete 22 is superior to athlete 33. Indeed athlete 22 ranks better than athlete 33 in the marathons 112244 and 55.
  • Athlete 33 is superior to athlete 11. Indeed athlete 33 ranks better than athlete 11 in the marathons 3344 and 55.

Explanation of the third test case: There are n=3n=3 athletes.

  • Athlete 11 is superior to athletes 22 and 33. Since he is superior to all other athletes, he is likely to get the gold medal.
  • Athlete 22 is superior to athlete 33.
  • Athlete 33 is not superior to any other athlete.

Explanation of the fourth test case: There are n=6n=6 athletes.

  • Athlete 11 is superior to athletes 334466.
  • Athlete 22 is superior to athletes 114466.
  • Athlete 33 is superior to athletes 224466.
  • Athlete 44 is not superior to any other athlete.
  • Athlete 55 is superior to athletes 1122334466. Since he is superior to all other athletes, he is likely to get the gold medal.
  • Athlete 66 is only superior to athlete 44.


Also read : What a Reversal solution codeforces

Leave a Comment