Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))


def get_sieve_of_eratosthenes(n):
    prime = []
    limit = 1000
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data=get_sieve_of_eratosthenes(1000000)
def prime_factorization(n):
    arr=[]
    for p in data:
        if p >n:
            break
        if n%p==0:
            arr.append(p)
        
    return arr

isPairwise = True
isSetwise = True
dict=defaultdict(lambda:0)

for i in range(N):
    test=A[i]
    for p in data:
        if p>A[i]:
            break
        if test%p==0:
            dict[p]+=1

for i in dict.values():
    if i==N:
        isPairwise=False
        isSetwise=False
    elif i>1:
        isPairwise=False
    else:
        pass

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
    


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

c=[0]*(10**6+5)

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000005):
    cnt=0
    for j in range(i,1000005,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

g=0
for i in range(N):
    g=gcd(g,A[i])
if g>1:
    isSetwise=False

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

from functools import reduce
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return (a*b)//gcd(a, b)


x = reduce(lcm, A)

ans = 0
for a in A:
    ans += x//a % MOD
    # ans %= MOD
print(ans % MOD)


### FIXED CODE ###

from collections import defaultdict
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    return retval


x = defaultdict(int)
for a in A:
    for p, q in factorization(a):
        if x[p] < q:
            x[p] = q

mod_x = 1
for p, q in x.items():
    mod_x *= pow(p, q, MOD)
mod_x %= MOD

B = [mod_x*pow(a, MOD-2, MOD) % MOD for a in A]
print(sum(B) % MOD)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n//r+1):
  for j in range(n//g+1):
    if (n-i*r-j*g)>=0 and (n-i*r-j*g)%b==0:
      ans=ans+1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n//r+1):
  for j in range((n-i*r)//g+1):
    if (n-i*r-j*g)>=0 and (n-i*r-j*g)%b==0:
      ans=ans+1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        S = S[::-1]
    else:
        if query[1] == '1':
            S = query[2]+S
        else:
            S = S+query[2]

print(S)


### FIXED CODE ###

#import time
S = input()
Q = int(input())
f = True
head = []
tail = []
for i in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        f = not f
    else:
        if (query[1] == '1' and f) or (query[1] == '2' and not f):
            head.append(query[2])
        else:
            tail.append(query[2])

S = ''.join(head)[::-1]+S+''.join(tail)
if not f:
    S = S[::-1]
print(S)

# start = time.time()
# elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
### BUGGY CODE ###

from collections import defaultdict
from copy import deepcopy

N,K=map(int,input().split())
AB=[0]*N
dic=defaultdict(int)
for i in range(N):
    a,b=map(int,input().split())
    if a in dic.keys():
        AB[dic[a]]=[a,AB[dic[a]][1]+b]
    else:
        dic[a]=i
        AB[i]=[a,b]
AB_=[]
for i in AB:
    if i==0:
        continue
    k=bin(i[0])[2:].zfill(30)
    AB_.append([k,i[1]])
AB=AB_
l=len(AB)

k=bin(K)[2:].zfill(30)
ans=0
for i in range(30):
    if k[i]=="1":
        t=k[:i]+"0"
        sum=0
        for j in range(l):
            if int(t)|int(AB[j][0][:i+1])<=int(t):
                sum+=AB[j][1]
        ans=max(ans,sum)
sum=0
t=k
for j in range(l):
    if int(t)|int(AB[j][0])<=int(t):
        sum+=AB[j][1]
ans=max(ans,sum)
print(ans)



### FIXED CODE ###

N,K=map(int,input().split())
AB=[]
for i in range(N):
    a,b=map(int,input().split())
    AB.append([a,b])
ans=sum([b for a,b in AB if K|a==K])

for i in range(int.bit_length(K)-1,0,-1):
    if not K &(1<<i):
        continue
    m=K & ~(1<<i)|(1<<i)-1
    s=sum([b for a,b in AB if m | a ==m])
    ans=max(s,ans)
print(ans)
### BUGGY CODE ###

n = int(input())
ai = [int(x) for x in input().split()]
bn = [0] * n
cn = [0] * n
dn = [0] * n

for i in range(0,n):
    j = n - 1 - i
    if (n//(j+1)<1):
        bn[j] = ai[j]
    else:
        bn[j] = (cn[j] + ai[j]) % 2

    if bn[j] == 1:
        for k in range(0,j):
            if (j+1)%(k+1) == 0:
                cn[k] += 1

m = sum(bn)
print(m)
for i in range(0,n):
    if bn[i] == 1:
        print(i+1, end=" ")


### FIXED CODE ###

n = int(input())
ai = [int(x) for x in input().split()]
bn = [0] * n

for i in range(0,n):
    j = n - 1 - i
    c = 0
    for k in range(2, n+1):
        idx = k * (j + 1) - 1
        if  idx > n-1:
            break
        c += bn[idx]
    
    bn[j] = (c + ai[j]) % 2


m = sum(bn)
print(m)
for i in range(0,n):
    if bn[i] == 1:
        print(i+1, end=" ")
### BUGGY CODE ###

MOD = 10**9 + 7
N,M = map(int,input().split(' '))
broken_list = [int(input()) for i in range(M)]

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append((ans[-2]+ans[-1]) % MOD)

print(ans[-1] % MOD)               

### FIXED CODE ###

MOD = 10**9 + 7
N,M = map(int,input().split(' '))
broken_list = set([int(input()) for i in range(M)])

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append((ans[-2]+ans[-1]) % MOD)

print(ans[-1] % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

def calc_lcs(X, Y):
    from array import array
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('I', [0] * (1001 * 1001))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1001 + j] = c[(i-1)*1001 + j - 1] + 1
            elif c[(i-1)*1001 + j] >= c[i*1001 + j - 1]:
                c[i*1001 + j] = c[(i-1)*1001 + j]
            else:
                c[i*1001 + j] = c[i*1001 + j - 1]
    return max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

import sys
import itertools
import collections


def search(H, W, S, start, end):
    wall_i = ord(b'#')
    used = [[-1 for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append(start)
    used[start[0]][start[1]] = 0

    while qu:
        h, w = qu.popleft()
        cost = used[h][w]
        for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
            if not (0 <= h0 < H and 0 <= w0 < W):
                continue
            if used[h0][w0] != -1:
                continue
            if S[h0][w0] == wall_i:
                continue

            if (h0, w0) == end:
                return cost + 1
            used[h0][w0] = cost + 1
            qu.append((h0, w0))
        cost += 1

    return -1


def resolve(in_):
    H, W = map(int, next(in_).split())
    S = tuple(s.strip() for s in itertools.islice(in_, H))

    road_i = ord(b'.')

    roads = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == road_i:
                roads.append((h, w))
    
    ans = max(search(H, W, S, start, end) for start, end in itertools.combinations(roads, 2))
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import itertools
import collections


def search(H, W, S, start):
    wall_i = ord(b'#')
    used = [[-1 for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append(start)
    used[start[0]][start[1]] = 0

    while qu:
        h, w = qu.popleft()
        cost = used[h][w]
        for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
            if not (0 <= h0 < H and 0 <= w0 < W):
                continue
            if used[h0][w0] != -1:
                continue
            if S[h0][w0] == wall_i:
                continue

            used[h0][w0] = cost + 1
            qu.append((h0, w0))

    return max(cost for costs in used for cost in costs)


def resolve(in_):
    H, W = map(int, next(in_).split())
    S = tuple(s.strip() for s in itertools.islice(in_, H))

    road_i = ord(b'.')

    roads = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == road_i:
                roads.append((h, w))
    
    ans = max(search(H, W, S, start) for start in roads)
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque

n=int(input())
lst=deque([])
counter=0
for _ in range(n):
    s=input()
    if s in lst : continue
    lst.append(s)
    counter+=1

print(counter)

### FIXED CODE ###

n=int(input())
lst=set([])
counter=0
for _ in range(n):
    s=input()
    if s in lst : continue
    lst.add(s)
    counter+=1

print(counter)
### BUGGY CODE ###

N = int(input())
S = str(input())
ans = set()
for i in range(7, 2**(N-1)+2**(N-2)+2**(N-3)+1):
    tmp = ''
    cnt = 0
    for j in range(0, N):
        if (i >> j) & 1:
            tmp += S[j]
            cnt += 1
        if cnt > 3:
            break
    if cnt == 3:
        ans.add(tmp)
print(len(ans))


### FIXED CODE ###

N = int(input())
S = str(input())
ans = 0
for i in range(0, 1000):
    x = str(i).zfill(3)
    try:
        idx1 = S.index(x[0])
        idx2 = S.index(x[1], idx1+1)
        idx3 = S.index(x[2], idx2+1)
        ans += 1
    except ValueError:
        continue
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main(N,C,S,F):
    ans = [0]*N
    for i in range(N-2):
        tmp = S[i]+C[i]
        for j in range(i+1,N-1):
            if tmp<S[j]:
                tmp = S[j]
            elif tmp>S[j] and (tmp-S[j])%F[j]!=0:
                part = F[j]
                while(1):
                    part += F[j]
                    if part>=tmp:
                        tmp = part
                        break
            
            tmp += C[j]
        ans[i] = tmp
    ans[-2] = C[-1]+S[-1]
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    N = int(input())
    C,S,F = [],[],[]
    for i in range(N-1):
        c,s,f = map(int, input().split())
        C.append(c)
        S.append(s)
        F.append(f)
    main(N,C,S,F)

### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

def main(N,C,S,F):
    ans = [0]*N
    for i in range(N-2):
        tmp = S[i]+C[i]
        for j in range(i+1,N-1):
            if tmp<S[j]:
                tmp = S[j]
            elif tmp>S[j] and (tmp-S[j])%F[j]!=0:
                part = math.ceil((tmp-S[j])/F[j])
                tmp = S[j]+F[j]*part
            tmp += C[j]
        ans[i] = tmp
    ans[-2] = C[-1]+S[-1]
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    N = int(input())
    C,S,F = [],[],[]
    for i in range(N-1):
        c,s,f = map(int, input().split())
        C.append(c)
        S.append(s)
        F.append(f)
    main(N,C,S,F)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import math
N, K = map(int, input().split())
aaa = [(-a, 1, -a) for a in map(float, input().split())]
heapify(aaa)
for _ in range(K):
    _, cnt, L = heappop(aaa)
    cnt += 1
    heappush(aaa, (L / cnt, cnt, L))
print(math.ceil(-aaa[0][0]))


### FIXED CODE ###

import numpy as np
import math
N, K = map(int, input().split())
aaa = np.array(list(map(float, input().split())), dtype='f8')
l = 0
r = 10 ** 9
while r != l:
    mid = (r + l) // 2
    bbb = aaa / mid
    bbb -= 1
    bbb = np.ceil(bbb)
    if bbb.sum() <= K:
        r = mid
    else:
        l = mid + 1
print(l)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list_min = sorted(A_list)

cnt = 0
A_baisu = []

for i in range(N-1):
    k = A_list_min[-1]//A_list_min[i]
    if A_list_min[i] == A_list_min[i+1]:
        A_baisu.append(A_list_min[i])
    if k >= 2:
        for j in range(2, k+1):
            if A_list_min[i]*j in A_list_min:
                A_baisu.append(A_list_min[i]*j)

A_baisu = list(set(A_baisu))
#print(A_baisu)

for i in range(len(A_baisu)):
    cnt += A_list_min.count(A_baisu[i])
ans = N - cnt        

print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
### BUGGY CODE ###

from collections import deque

n, m  = map(int, input().split())
g     = {}
maxD  = [-1 for i in range(n)]
color = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)


### FIXED CODE ###

n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)
### BUGGY CODE ###

from fractions import gcd
N, M = map(int, input().split())
if M%N==0:
  print(M//N)
else:
  c = M%N
  b = M//N
  ls = []
  ans = 0
  for i in range(1,b+1):
    x = M - i*N
    if gcd(i,x)>ans:
      ans = gcd(i,x)
  print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
ls = []
for i in range(1,M+1):
  if M%i==0:
    j = M//i
    if i<=M//N:
      ls += [i]
    if j<=M//N:
      ls += [j]
  if M**0.5<i:
    break
print(max(ls))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n,k = map(int,input().split())
ls = np.array(list(map(int,input().split())))
inf = float("inf")
dp = [inf] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
for i in range(2,n):
    st = max(0,i-k)
    dp[i] = np.min(dp[st:i]+abs(ls[i]-ls[st:i]))
print(int(dp[n-1]))

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    lr = []
    for _ in range(k):
        lr.append(tuple(map(int, input().split())))
    mod = 998244353
    
    dp = [0]*n
    dp[0] = 1
    
    acc = [0]*n
    acc[0] = 1
    
    for i in range(1, n):
        for l, r in lr:
            if 0 <= i-r and i-l < i:
                dp[i] += acc[i-l]-acc[i-r-1]
            elif i-r < 0 and i-l < i:
                dp[i] += acc[i-l]
            elif i-r < 0 and i <= i-l:
                dp[i] += acc[i-1]
            elif 0 < i-r and i <= i-l:
                dp[i] += acc[i-1]-acc[i-r-1]
        acc[i] = acc[i-1]+dp[i]
    
    print(dp[-1]%mod)


main()

### FIXED CODE ###

n, k = map(int, input().split())
lr = []
for _ in range(k):
    lr.append(tuple(map(int, input().split())))
mod = 998244353

dp = [0]*n
dp[0] = 1

acc = [0]*n
acc[0] = 1

for i in range(1, n):
    for l, r in lr:
        if 0 <= i-r and i-l < i:
            dp[i] += acc[i-l]-acc[i-r-1]
        elif i-r < 0 and i-l < i:
            dp[i] += acc[i-l]
        elif i-r < 0 and i <= i-l:
            dp[i] += acc[i-1]
        elif 0 < i-r and i <= i-l:
            dp[i] += acc[i-1]-acc[i-r-1]
    acc[i] = acc[i-1]+dp[i]%mod

print(dp[-1]%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)

### FIXED CODE ###

import time
start = time.time()

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    if time.time() - start > 1.8:
        print(N * (N - 1) // 2)
        exit()

    cnt += 1

print(cnt)