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

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    for j in range(n):
        TB[i][j] = B[j][i]
        
import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=np.count_nonzero(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1))%mod)%mod *pow(2,-1,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)
    
     


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [((A[i]>>(59-j))) & 1 for j in range(60)]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


print((ans)%mod)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
T = [[0]*N for _ in range(N)]
for _ in range(M):
    l,r = map(int,input().split())
    T[l-1][r-1] += 1
def f(x,y,T):
    ret = 0
    for i in range(y):
        for j in range(x):
            ret += T[i][j]
    return ret
query = []
res = []
for _ in range(Q):
    p,q = map(int,input().split())
    res.append(f(q,q,T) - f(p-1, q ,T)- f(q, p-1, T) + f(p-1, p-1, T))
for r in res:
    print(r)

### FIXED CODE ###

import sys
from itertools import accumulate
n,m,q = map(int,input().split())
ipt = sys.stdin.readlines()
rails = [[0]*n for _ in range(n)]
for line in ipt[:m]:
    l,r = map(int,line.split())
    rails[l-1][r-1] += 1
rails = [accumulate(s) for s in rails]
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*rails)]
buf = []
for  line in ipt[m:]:
    p,q = map(int,line.split())
    buf.append(rails[q-1][p-1])
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

N,M = map(int,input().split())
ab = []
start = []
goal = []
for i in range(M):
    ab.append(list(map(int,input().split())))
    if ab[i][0] == 1:
        start.append(ab[i][1])
    if ab[i][1] == N:
        goal.append(ab[i][0])
ans = 'IMPOSSIBLE'
for i in start:
    if i in goal:
        ans = 'POSSIBLE'
print(ans)


### FIXED CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
X = [input() for _ in range(H)]
maxloc = -10

def bfs(sx, sy, gx, gy):
  dist = [[-1]*W for _ in range(H)]
  dist[sx-1][sy-1] = 0
  q = deque([(sx-1, sy-1)])
  while q:
    u, v = q.popleft()
    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
      if not(0 <= u+i < H and 0 <= v+j < W):
        continue
    
      if(dist[u+i][v+j] >= 0 or X[u+i][v+j] == "#"):
        continue

      dist[u+i][v+j] = dist[u][v]+1
      q.append((u+i, v+j))

  return dist[gx-1][gy-1]

for i in range(H):
  for j in range(W):
    sx = i
    sy = j
    for k in range(H):
      for l in range(W):
        gx = k
        gy = l
        if(bfs(i+1, j+1, k+1, l+1) > maxloc):
          maxloc = bfs(i+1, j+1, k+1, l+1)
          
print(maxloc)

### FIXED CODE ###

def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['#'] * (W+2) for _ in range(H+2)]
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    s = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '#'):
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    for i in range(H+2):
      for j in range(W+2):
        if(dist[i][j] >= 0):
          s = max(s, dist[i][j])
    return s

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      if(graph[sx][sy] == '.'):
          tmp = dfs(sx, sy)
          ans = max(ans, tmp)
          
  print(ans)
  
main()
### BUGGY CODE ###

from sys import exit
from fractions import gcd

def segfunc(x, y):
    '''
    問題に応じて返り値を設定
    '''
    return gcd(x, y)


def init(a):
    '''
    配列aで初期化
    '''
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def query(p, q):
    '''
    [p, q)についてsegfuncを適用したものを返す
    '''
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


n, k = map(int, input().split())
a = list(map(int, input().split()))

if k > max(a):
    print('IMPOSSIBLE')
    exit()

num = (2 ** len(bin(n - 1)) - 2)
ide_ele = 0
seg = [ide_ele] * 2 * num

init(a)

if k % query(0, n) == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

from sys import exit
from math import gcd

def segfunc(x, y):
    '''
    問題に応じて返り値を設定
    '''
    return gcd(x, y)


def init(a):
    '''
    配列aで初期化
    '''
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])


def query(p, q):
    '''
    [p, q)についてsegfuncを適用したものを返す
    '''
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(res, segfunc(seg[p], seg[q]))
    
    return res


n, k = map(int, input().split())
a = list(map(int, input().split()))

if k > max(a):
    print('IMPOSSIBLE')
    exit()

num = (2 ** len(bin(n - 1)) - 2)
ide_ele = 0
seg = [ide_ele] * 2 * num

init(a)

if k % query(0, n) == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[i]<L[j]+L[k] and L[j]<L[i]+L[k] and L[k]<L[i]+L[j]:
                ans+=1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))

L.sort()
result=0
for i in range(N-2):
    for j in range(i+1,N-1):
        result+=bisect_left(L,L[i]+L[j])-j-1
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = {i:[] for i in range(1,c+1)}
table = [0 for _ in range(200004)]
for _ in range(n):
    s,t,c = map(int, input().split())
    channels[c].append([s,t])

for ch, time in channels.items():
    sub = [0 for _ in range(200004)]
    for s,t in time:
        if sub[s*2]:
            sub[s*2] = 0
        else:
            sub[s*2-1] = 1
        if sub[t*2-1]:
            sub[t*2-1] = 0
        else:
            sub[t*2] = -1
    for i in range(1,200002):
        sub[i] += sub[i-1]
        table[i] += max(0, sub[i])
ans = 0
for i in range(1,200002):
    ans = max(ans, table[i])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = {i:[] for i in range(1,c+1)}
table = [0 for _ in range(200004)]
for _ in range(n):
    s,t,c = map(int, input().split())
    channels[c].append([s,t])

for ch, time in channels.items():
    sub = [0 for _ in range(200004)]
    for s,t in time:
        if sub[s*2]:
            sub[s*2] = 0
        else:
            sub[s*2-1] = 1
        if sub[t*2-1]:
            sub[t*2-1] = 0
        else:
            sub[t*2] = -1
    for i in range(1,200002):
        sub[i] += sub[i-1]
        table[i] += max(0, sub[i])
ans = 0
for i in range(1,200002):
    ans = max(ans, table[i])
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    alist = sorted(list(aset))
    for al in alist:
        if al == '':
            continue
        c += 1
        if c == K:
            ans = al
            break
    if c == K:
        break

print(ans)

### FIXED CODE ###

def main():
    S = input()
    N = len(S)
    K = int(input())

    S1 = {}
    for i, s in enumerate(S):
        if not s in S1.keys():
            S1[s] = [i]
        else:
            S1[s].append(i)
    alp = sorted(list(S1.keys()))

    c = 0
    for a in alp:
        aset = set()
        inds = S1[a]
        for d in inds:
            up = min(N-d+1, K+1)
            for i in range(up):
                aset.add(S[d:d+i])
        L = len(aset)-1
        if L >= K-c:
            break
        c += L

    for _ in range(10):
        M = '何だこれはもうやめてくれよ'
        for a in aset:
            if a < M:
                M = a
        aset.discard(M)
        if M == '':
            continue
        c += 1
        if c >= K:
            ans = M
            break

    print(ans)



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

n,q = map(int,input().split())
x = list([0] * n for i in range(n))
for _ in range(n-1):
  a,b  = map(int,input().split())
  a -= 1
  b -= 1
  x[a][b] += 1
  x[b][a] += 1
  for i in range(b-1):
    if x[a][i] == 1:
      x[i][b] += 1
shio = [0] *n
for j in range(q):
  a,b =map(int,input().split())
  a -= 1
  shio[a] += b
  for k in range(a,n):
    if x[a][k] == 1:
      shio[k] += b
for i in range(n):
  print(shio[i])
    
    
    
  

### FIXED CODE ###

N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1

min_A = min(A)
A = sorted(A, reverse=True)

if min_A == 0:
    print(0)
    exit()

for a in A:
    ans *= a
    if ans > 10 ** 18:
        break

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

INF = 10 ** 8

H, N = map(int, input().split())

dp = [INF] * (H + 1)
dp[0] = 0

for _ in range(N):
    A, B = map(int, input().split())
    for h in range(H):
        dp[min(H, h + A)] = min(dp[min(H, h + A)], dp[h] + B)

print(dp[H])


### FIXED CODE ###

def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    h, n = map(int, input().split())
    *ab, = (list(map(int, input().split())) for _ in range(n))

    dp = [[inf] * (h + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    # dp[使った魔法][与えたダメージ]=最小魔法消費

    for i, (a, b) in enumerate(ab):
        for hp in range(h + 1):
            if hp < a:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][0] + b)
            else:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][hp - a] + b)

    print(dp[n][h])


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)'''
def yakusuu(n):
    #約数リスト生成,バラバラに出るので.sort()を使う必要あるかも
    #PyPy推奨
    yakusuu_list = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yakusuu_list.append(i)
            if i != n // i:
                yakusuu_list.append(n//i)
    return yakusuu_list

n=int(input())
a=list(map(int, input().split()))
#print(sorted(a))
a.sort()
wa=[a[0]]
waaa=[False]*(10**6)
bl=[]

def ok(wa,waaa,item,bl):
    m=yakusuu(item)
    #print(m)
    if waaa[item-1]==True:
        bl.append(item-1)
        return

    waaa[item-1]=True

    for jtem in m:
        if jtem!=item and waaa[jtem-1]==True:
            bl.append(item-1)
            return

    waaa[item-1]=True
    #print(item,waaa[:25])
    return

for item in a:
    ok(wa,waaa,item,bl)

#import collections
print(waaa.count(True)-len(set(bl)))
#print(max(0,len(wa)-len(set(bl))))


### FIXED CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for i in range(n):
    if ll[a[i]]==1:
        if l[a[i]]:
            ans+=1

print(ans)
### BUGGY CODE ###

mod = 10**9+7
S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
for ind,s in enumerate(S):
    if(s=='?'):
        for i in range(10):
            for j in range(13):
                dp[ind+1][(j*10+i)%13] += dp[ind][j]
                dp[ind+1][(j*10+i)%13] %= mod
    else:
        for j in range(13):
            dp[ind+1][(j*10+int(s))%13] += dp[ind][j]
            dp[ind+1][(j*10+int(s))%13] %= mod
print(dp[len(S)][5])

### FIXED CODE ###

mod = 10**9+7
S = input()
n = len(S)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for ind,s in enumerate(S):
    if(s=='?'):
        for i in range(10):
            for j in range(13):
                dp[ind+1][(j*10+i)%13] += dp[ind][j]
                dp[ind+1][(j*10+i)%13] %= mod
    else:
        for j in range(13):
            dp[ind+1][(j*10+int(s))%13] += dp[ind][j]
            dp[ind+1][(j*10+int(s))%13] %= mod
print(dp[n][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [N//i for i in range(1, N+2)]
for j, a in enumerate(A_[1:], 1):
    for i in range(N):
        d = a//(i+1)
        if Ans[i+j] > d:
            Ans[i+j] = d
        if d==0:
            break
del Ans[-1]
print("\n".join(map(str, Ans)))


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N+1)
    Cnt_A = [0] * (N+1)
    for a in A:
        Cnt_A[a] += 1
        cnt = Cnt_A[a]
        C[cnt] += 1
    cum_C = []
    cu = 0
    for c in C:
        cu += c
        cum_C.append(cu)
    Ans = []
    for k in range(1, N+1):
        # K = k のとき、 n 組以上作れる <=> 使えるカードが nk 枚以上
        # n 組以上作れる <=> 同じカードは n 枚以下
        # 同じカードは n 枚以下で全体として nk 枚以上用意できるか？
        ok, ng = 0, N//k+1
        while ok + 1 < ng:
            n = ok+ng>>1
            if cum_C[n] >= n*k:
                ok = n
            else:
                ng = n
        Ans.append(ok)
    print("\n".join(map(str, Ans)))

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

n,q=map(int,input().split())
c=list(map(int,input().split()))
ques=[]
from collections import defaultdict
ans=defaultdict(int)
for _ in range(q):
    l,r=map(int,input().split())
    ques.append((l,r))

sortques=sorted(ques)
sortques=sorted(sortques, key=lambda x:x[1])

good=BIT(n+1)
goodind=[-1]*n
last=0
for x in range(q):
    l,r=sortques[x]
    for i in range(last, r):
        if goodind[c[i]-1]==-1:
            goodind[c[i]-1]=i
            good.add(i+1, 1)
        else:
            j=goodind[c[i]-1]
            good.add(j+1, -1)
            goodind[c[i]-1]=i
            good.add(i+1, 1)
    ans[(l,r)]=good.get(l-1,r)
    last=r

for i in range(q):
    print(ans[ques[i]])

### FIXED CODE ###

import sys
input = sys.stdin.readline
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

n,q=map(int,input().split())
c=list(map(int,input().split()))
ques=[]
from collections import defaultdict
ans=defaultdict(int)
for _ in range(q):
    l,r=map(int,input().split())
    ques.append((l,r))

sortques=sorted(ques, key=lambda x:x[1])

good=BIT(n+1)
goodind=[-1]*n
last=0
for x in range(q):
    l,r=sortques[x]
    if last!=r:
        for i in range(last, r):
            if goodind[c[i]-1]==-1:
                goodind[c[i]-1]=i
                good.add(i+1, 1)
            else:
                j=goodind[c[i]-1]
                good.add(j+1, -1)
                goodind[c[i]-1]=i
                good.add(i+1, 1)
    ans[(l,r)]=good.get(l-1,r)
    last=r

for i in range(q):
    print(ans[ques[i]])
### BUGGY CODE ###

from collections import Counter as C
N, M = map(int, input().split())
A = [[int(a)-1 for a in input().split()] for _ in range(N)]
X = [1] * M
mi = 1 << 100
for i in range(M):
    c = C([min([(j, A[i][j]) for j in range(M) if X[A[i][j]]])[1] for i in range(N)])
    a = max([(c[a], a) for a in c])[1]
    mi = min(mi, c[a])
    X[a] -= 1
print(mi)

### FIXED CODE ###

from collections import Counter as C
N, M = map(int, input().split())
A = [[int(a)-1 for a in input().split()] for _ in range(N)]
X = [1] * M
mi = 1 << 100
for i in range(M):
    c = C([min([(j, A[i][j]) for j in range(M) if X[A[i][j]]])[1] for i in range(N)])
    a = max([(c[a], a) for a in c])[1]
    mi = min(mi, c[a])
    X[a] -= 1
print(mi)
### BUGGY CODE ###

A,B = [int(i) for i in input().split()]

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

def get_sieve_of_eratosthenes(n):#n以下の素数のリストを返す
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return(data)

n=gcd(A,B)
ans = 1
if n==1:
    print(1)
else:
    plist = get_sieve_of_eratosthenes(n)
    for p in plist:
        if n==1:
            break
        if n%p==0:
            n = n//p
            ans+=1
    print(ans)

### FIXED CODE ###

A,B = [int(i) for i in input().split()]

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

def get_sieve_of_eratosthenes(n):#n以下の素数のリストを返す
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return(data)

n=gcd(A,B)
ans = 1
if n==1:
    print(1)
else:
    #plist = get_sieve_of_eratosthenes(n)
    #for p in plist:
    for p in range(2,int(n**0.5)+3):
        if n%p==0:
            ans+=1
            while n%p==0:
                n = n//p
    if n!=1:
        ans+=1
    print(ans)
### BUGGY CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1

start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]
print(max(dfs(n, edges) for n in start_nodes))


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

"""
"""
n,x,y=map(int,input().split())
k_mins=[]
for i in range(1,n):
    for j in range(i+1,n+1):
        k_mins.append(min(j-i,abs(x-i)+1+abs(y-j),abs(x-j)+1+abs(y-i)))

ret=[]
for i in range(1,n):
    #[i for i in l if not i % 2 == 0]
    ret.append(len([ki for ki in k_mins if ki == i]))
for r in ret:
    print(r)




### FIXED CODE ###

"""
"""
n,x,y=map(int,input().split())
ret=[0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        ret[min(j-i,abs(x-i)+1+abs(y-j),abs(x-j)+1+abs(y-i))-1]+=1
for r in ret:
    print(r)