B. Забег за золотом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Олимпийские игры только что начались, и Федерико с нетерпением ждет начала марафонского забега.

В марафоне будут участвовать $$$n$$$ спортсменов, от $$$1$$$ до $$$n$$$, и все они в прошлом участвовали в $$$5$$$ важных марафонах, пронумерованных от $$$1$$$ до $$$5$$$. Для каждого $$$1\le i\le n$$$ и $$$1\le j\le 5$$$ Федерико помнит, что спортсмен $$$i$$$ занял место $$$r_{i,j}$$$ в марафоне $$$j$$$ (например, $$$r_{2,4}=3$$$ означает, что спортсмен $$$2$$$ был третьим в марафоне $$$4$$$).

Федерико считает, что спортсмен $$$x$$$ превосходит спортсмена $$$y$$$, если спортсмен $$$x$$$ занял лучшее место, чем спортсмен $$$y$$$, по крайней мере в $$$3$$$ прошлых марафонах, т.е. $$$r_{x,j}<r_{y,j}$$$ по крайней мере для $$$3$$$ различных значений $$$j$$$.

Федерико считает, что у спортсмена хорошие шансы получить золотую медаль на Олимпийских играх, если он превосходит всех остальных спортсменов.

Найдите любого спортсмена, у которого хорошие шансы получить золотую медаль (то есть спортсмена, который превосходит всех остальных спортсменов), или определите, что такого спортсмена нет.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 50\,000$$$) — количество спортсменов.

Затем следуют $$$n$$$ строк, каждая из которых описывает места одного спортсмена.

$$$i$$$-я из этих строк содержит $$$5$$$ целых чисел $$$r_{i,1},\,r_{i,2},\,r_{i,3},\,r_{i,4},\, r_{i,5}$$$ ($$$1\le r_{i,j}\le 50\,000$$$) — места спортсмена $$$i$$$ в последних $$$5$$$ марафонах. Гарантируется, что в каждом из $$$5$$$ прошедших марафонов $$$n$$$ спортсменов заняли различные места, т.е. для каждого $$$1\le j\le 5$$$, $$$n$$$ значений $$$r_{1,j},\, r_{2, j},\, \dots,\, r_{n, j}$$$ попарно различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$50\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — номер спортсмена, у которого хорошие шансы получить золотую медаль (то есть спортсмена, который превосходит всех остальных спортсменов). Если таких спортсменов нет, выведите $$$-1$$$. Если таких спортсменов больше, чем один, выведите любого из них.

Пример
Входные данные
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
Выходные данные
1
-1
1
5
Примечание

Объяснение первого набора входных данных: Есть только один спортсмен, поэтому он превосходит всех остальных (так как больше никого нет), и поэтому у него хорошие шансы получить золотую медаль.

Пояснение второго набора входных данных: Есть $$$n=3$$$ спортсменов.

  • Спортсмен $$$1$$$ превосходит спортсмена $$$2$$$. Действительно, спортсмен $$$1$$$ лучше спортсмена $$$2$$$ в марафонах $$$1$$$, $$$2$$$ и $$$3$$$.
  • Спортсмен $$$2$$$ превосходит спортсмена $$$3$$$. Действительно, спортсмен $$$2$$$ превосходит спортсмена $$$3$$$ в марафонах $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$.
  • Спортсмен $$$3$$$ превосходит спортсмена $$$1$$$. Действительно, спортсмен $$$3$$$ лучше, чем спортсмен $$$1$$$ в марафонах $$$3$$$, $$$4$$$ и $$$5$$$.

Объяснение третьего набора входных данных: Есть $$$n=3$$$ спортсменов.

  • Спортсмен $$$1$$$ превосходит спортсменов $$$2$$$ и $$$3$$$. Поскольку он превосходит всех остальных спортсменов, у него хорошие шансы получить золотую медаль.
  • Спортсмен $$$2$$$ превосходит спортсмена $$$3$$$.
  • Спортсмен $$$3$$$ не превосходит ни одного другого спортсмена.

Пояснение четвертого набора входных данных: Есть $$$n=6$$$ спортсменов.

  • Спортсмен $$$1$$$ превосходит спортсменов $$$3$$$, $$$4$$$, $$$6$$$.
  • Спортсмен $$$2$$$ превосходит спортсменов $$$1$$$, $$$4$$$, $$$6$$$.
  • Спортсмен $$$3$$$ превосходит спортсменов $$$2$$$, $$$4$$$, $$$6$$$.
  • Спортсмен $$$4$$$ не превосходит ни одного другого спортсмена.
  • Спортсмен $$$5$$$ превосходит спортсменов $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$6$$$. Поскольку он превосходит всех остальных спортсменов, у него хорошие шансы получить золотую медаль.
  • Спортсмен $$$6$$$ превосходит только спортсмена $$$4$$$.