1-indexedで説明します。

題意(意訳)

n 人の人がいる。これらの人は過去に5回の試合に出ており、その順位が与えられる。順位はdistinct(同順はない)である。
チャンピオンとは、3つ以上の試合において、他のどんな人よりも順位が強い(数値としては低い)人のことである。各試合の間に優劣はない(ポイントの高い試合、などはない)
チャンピオンがいるならその人を述べよ(複数いるならどれでもいい)。いないならそれを述べよ
- ※後述の通り、複数の候補が存在することはありません

こう考えた前提

まず、(aがbに)勝つをaはbより順位が強い試合が3つ以上あると定義します。

さて、問題のポイントは、チャンピオンがいるなら、１人に定まるです。なぜなら、チャンピオン$a$がいるとするなら、その人は3つ以上の試合の順位がほかのすべての人より強いです。もしも、他のチャンピオン$b$がいるとすると、その人は$a$に勝てる試合が3つ以上あることになりますが、これは前提に反します。

ただし、サンプルにある通り、チャンピオンがいない場合もあるです。

こう考えた STEP1 チャンピオン候補を決める

STEP1では、チャンピオンがいると仮定します。(この仮定で処理を進めるのがとても重要！)

まず、人$1$をチャンピオンと仮定して、人$2,3,..,n$と比較します。もし、すべてに勝ったなら、人$1$がチャンピオンです。もし、人$k$に負けたとすると、人$k$がチャンピオンかもしれないので、人$k$を基準にして$人k+1, k+2,..n$と比較します。これを繰り返します。$O(N)$です。

こうして最後に残った(最後まで処理した)チャンピオン候補kは真にチャンピオンとは限りません.
$k$よりも前の人に負けることがあるからです。ただし、チャンピオンがいるとするならば、最後に残ったチャンピオン$k$が答えです。なぜなら、前提の通り、チャンピオンはほかの人に負けるはずがないので、どういう順序(例えばソートされても)で上記の施行をしても絶対に最後まで残ります。

こう考えた STEP2 チャンピオンかを確かめる

そこで、チャンピオンかを判定します。候補$k$を$k$を除く$1,2,..,n$と愚直に比較します。すべてに勝てればチャンピオンです。$O(N)$です。

サンプル2の通り、途中で負けることがありますが、この場合は-1(チャンピオンはいない)です。他に本当のチャンピオンがいることはありません。STEP1後段の通り、それが存在するなら、$k$はそれに負けています。

実装

結果、$O(N)$で解けました。

私はSTEP1がうまく思い浮かばず、トーナメント形式でSTEP1を処理しました。(2人ずつ取っていき、買ったほうだけ次のリストに残す方法です)。

from copy import deepcopy
def do():
    n = int(input())
    dat = []
    for i in range(n):
        l = map(int, input().split())
        l = list(l)
        l.append(i)
        dat.append(l)
    odat = deepcopy(dat)
    
    # STEP1: 
    while len(dat) > 1:
        newdat = []
        for i in range(0, len(dat), 2):
            ls = dat[i:i+2]
            if len(ls) == 1:
                newdat.append(ls[0])
                continue
            a = ls[0]
            b = ls[1]
            cnt = 0
            for i in range(5):
                if a[i] < b[i]:
                    cnt += 1
            if cnt >= 3:
                newdat.append(ls[0])
            else:
                newdat.append(ls[1])
        dat = newdat

    # STEP2
    candidate = dat[0]
    for x in odat:
        cnt = 0
        for i in range(5):
            if candidate[i] <= x[i]:
                cnt += 1
        if cnt >= 3:
            continue
        print("-1")
        return
    print(candidate[5] + 1)

q = int(input())
for _ in range(q): do()