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

class LcpArr(object):
    def __init__(self, orig_str: str):
        self.orig_str = orig_str
        self.sufs = self.__create_sufs()
        self.suf_arr, self.lcp_arr = self.__create_arr()

    def __call__(self, i: int, j: int):
        si, sj = sorted([self.suf_arr.index(i), self.suf_arr.index(j)])
        return min(self.lcp_arr[si:sj])

    def __create_sufs(self):
        n = len(self.orig_str)
        return [self.orig_str[i:] for i in range(n)] + [""]

    def __create_arr(self):
        n = len(self.orig_str)
        suf_arr = sorted(range(n), key=lambda x: self.sufs[x]) + [n]

        lcp_arr = [-1]*n
        for i in range(n):
            si = suf_arr.index(i)
            lcp_arr[si] = self.__lcp_len(i, suf_arr[si+1])

        return suf_arr, lcp_arr

    def __lcp_len(self, i: int, j: int):
        suf, next_suf = self.sufs[i], self.sufs[j]

        l = 0
        for i in range(min(len(suf), len(next_suf))):
            if suf[i] != next_suf[i]:
                break
            l += 1
        return l

def f_e():
    n = int(input())
    s = input()
    lcp = LcpArr(s)
    a = 0
    for i in range(n):
        for j in range(n):
            if i>=j:
                continue
            a = max(a, min(lcp(i, j), j-i))
    print(a)

if __name__ == "__main__":
    f_e()


### FIXED CODE ###

def f_e_dp():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if s[i]==s[j] and i<j:
                dp[i][j] = dp[i+1][j+1]+1
    a = 0
    for i in range(n):
        for j in range(n):
            if i<j:
                a = max(a, min(j-i, dp[i][j]))
    print(a)

if __name__ == "__main__":
    f_e_dp()
### BUGGY CODE ###

n, m = map(int,input().split())
List = list(map(int,input().split()))
List.sort(reverse=True)
halves = [0]
max_halves = 0

for i in range(m):
  x = List.pop(0)
  if x >= max_halves:
    x = int(x/2)
    if len(List) == 0:
      List = [x]
    else:
      halves.append(x)
      if x >= max_halves:
        max_halves = x
  else:
    halves.remove(max_halves)
    halves.append(int(max_halves/2))
    max_halves = max(halves)
    List = [x]+ List
print(sum(List)+sum(halves))


### FIXED CODE ###

import heapq
n, m = map(int,input().split())
List = list(map(int,input().split()))

List = list(map(lambda x: x*(-1), List))  # 各要素を-1倍

heapq.heapify(List)
for i in range(m):
  max = heapq.heappop(List)
  heapq.heappush(List, int(max/2))  # 要素の挿入
print(sum(List)*(-1))
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
for i in range(2, 10 ** 12 + 1):
    if C == 1:
        break
    while True:
        if C % i != 0:
            break
        if i not in ans:
            ans.append(i)
        C //= i
print(len(ans) + 1)


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)
### BUGGY CODE ###

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

N, M = map(int, raw_input().split())
_count = [0]*N

for i in range(M):
    L, R = map(int, raw_input().split())
    for j in range(L-1,R):
        _count[j] += 1

print _count.count(M)

### FIXED CODE ###

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

N, M = map(int, raw_input().split())
_L = 1
_R = N

for i in range(M):
    L, R = map(int, raw_input().split())
    if _L < L:
        _L = L
    if R < _R:
        _R = R 

print str(max(_R-_L+1,0))
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse = True)

def judge(a:int, b:int, c:int):
    if a < b + c:
        pass
    else:
        return False
    if b < c + a:
        pass
    else:
        return False
    if c < a + b:
        pass
    else:
        return False
    return True

def binary_search(l:int, r:int):
    while r - l > 1:
        mid = (l + r) // 2
        c = L[mid]
        if judge(a, b, c) == True:
            l = mid
        else:
            r = mid
    return l

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        f1 = judge(a, b, L[j + 1])
        f2 = judge(a, b, L[n - 1])
        if f1 == True:
            if f2 == False:
                ans += binary_search(j, n - 1) - j 
            else:
                ans += n - j - 1
        else:
            pass
    
print(ans)

### FIXED CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse = True)

def judge(a:int, b:int, c:int):
    if a < b + c:
        pass
    else:
        return False
    if b < c + a:
        pass
    else:
        return False
    if c < a + b:
        pass
    else:
        return False
    return True

def binary_search(l:int, r:int):
    while r - l > 1:
        mid = (l + r) // 2
        c = L[mid]
        if judge(a, b, c) == True:
            l = mid
        else:
            r = mid
    return l

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        f1 = judge(a, b, L[j + 1])
        f2 = judge(a, b, L[n - 1])
        if f1 == True:
            if f2 == False:
                ans += binary_search(j, n - 1) - j 
            else:
                ans += n - j - 1
        else:
            pass
    
print(ans)
### BUGGY CODE ###

from sys import stdin
import bisect

N,Q = list(map(int,stdin.readline().strip().split()))
S = input().strip()

for i in range(Q):
    l,r = list(map(int,stdin.readline().strip().split()))
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

from sys import stdin
import bisect

N,Q = list(map(int,stdin.readline().strip().split()))
S = input().strip()

P = [0]*N
cnt = 0

for i in range(1,N):
    if S[i-1:i+1] == 'AC':
        cnt+=1
    P[i] = cnt

for i in range(Q):
    l,r = list(map(int,stdin.readline().strip().split()))
    print(P[r-1] - P[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
for i in range(N):
    a = A.pop(0)
    B.append(a)
    B.append(a)
ans = 0
B.pop()
for i in range(N-1):
    a = B.pop()
    ans += a
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
k = N - 2
a = A.pop()
ans = a
n = k // 2
for i in range(n):
    a = A.pop()
    ans += 2*a
if k - 2*n == 1:
    ans += A[-1]

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

_,d=open(0)
*d,=map(int,d.split())
e=[0]*10**5
for i in d:e[i]+=1
a=d[0]<1==e[0]
for x,y in zip(e,e[1:]):a*=x**y
print(a%998244353)

### FIXED CODE ###

_,d=open(0)
*d,=map(int,d.split())
e=[0]*-~max(d)
for i in d:e[i]+=1
a=d[0]<1==e[0]
for x,y in zip(e,e[1:]):a*=x**y
print(a%998244353)
### BUGGY CODE ###

import numpy as np

N = int(input())
dp = [float("inf")]*(N + 1)
dp[0] = 0
pull_list_9 = [9**i for i in range(1, 6)]
pull_list_6 = [6**i for i in range(1, 7)]
pull_list = np.array(pull_list_9 + pull_list_6 + [1])
p_s = sorted(pull_list)
for i in range(1, N + 1):
  for j in p_s:
    if i - j < 0:
      break
    dp[i] = min(dp[i], dp[i-j] + 1)
print(dp[-1])


### FIXED CODE ###

N = int(input())
dp = [float("inf")]*(N + 1)
dp[0] = 0
pull_list_9 = [9**i for i in range(1, 6)]
pull_list_6 = [6**i for i in range(1, 7)]
pull_list = pull_list_9 + pull_list_6 + [1]
p_s = sorted(pull_list)

for i in range(1, N + 1):
  for j in p_s:
    if i - j < 0:
      break
    dp[i] = min(dp[i], dp[i-j] + 1)

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

import collections

n = int(input())
s = [input() for i in range(n)]

counter = collections.Counter(s)
ans = []
for i in sorted(list(counter.keys())):
    if counter[i] == counter.most_common()[0][1]:
        print(i)

### FIXED CODE ###

import collections
 
n = int(input())
s = [input() for i in range(n)]
 
counter = collections.Counter(s)
most = counter.most_common()
ans = []
for i in range(len(counter.keys())):
    if most[i][1] == most[0][1]:
        ans.append(most[i][0])
    else:
        break
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

class Sets:
  def __init__(self):
    self.sets = []
  def get_group(self, a):
    if a < 0: return -1
    for i in range(len(self.sets)):
      if a in self.sets[i]:
        return i
    return -1
  def add_same_pair(self, a, b):
    ga = self.get_group(a)
    gb = self.get_group(b)
    if ga < 0 and gb < 0:
      self.sets.append(set([a,b]))
    elif ga == gb:
      return
    elif ga >= 0 and gb < 0:
      self.sets[ga].add(b)
    elif ga < 0 and gb >= 0:
      self.sets[gb].add(a)
    else:
      gmin = min(ga,gb)
      gmax = max(ga,gb)
      s = self.sets.pop(gmax)
      self.sets[gmin] = self.sets[gmin].union(s)
  def __str__(self):
    return str(self.sets)

N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
road_sets = Sets()
rail_sets = Sets()

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

combi_counts = {}
for i in range(N):
  g_road = road_sets.get_group(i)#roads[i])
  g_rail = rail_sets.get_group(i)#rails[i])
  if g_road < 0 or g_rail < 0:
    continue
  if (g_road,g_rail) in combi_counts:
    combi_counts[(g_road,g_rail)] += 1
  else:
    combi_counts[(g_road,g_rail)] = 1

result = []
for i in range(N):
  g_road = road_sets.get_group(i)
  g_rail = rail_sets.get_group(i) 
  if g_road < 0 or g_rail < 0:
    result.append(1)
  else:
    result.append(combi_counts[(g_road,g_rail)])
print ' '.join(map(str, result))

### FIXED CODE ###

from collections import Counter
N,K,L = map(int,input().split())

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

def root(a,par):
    if a == par[a]: return a
    par[a] = root(par[a],par)
    return par[a]

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))
### BUGGY CODE ###

N = int(input())
S0 = input()
S = [S0[i] for i in range(N)]
minimum = N + 1

for i in range(N+1):
    m = 0
    for k in range(i):
        if S[k] != '.':
            m += 1
    for k in range(i, N):
        if S[k] != '#':
            m += 1
    if m < minimum:
        minimum = m

print(minimum)

### FIXED CODE ###

from copy import deepcopy

N = int(input())
S = input()
M = [0 for i in range(N+1)]

for i in range(N):
    if S[i] != '#':
        M[0] += 1

mini = deepcopy(M[0])
    
for i in range(N):
    if S[i] == '#':
        M[i+1] = M[i] + 1
    else:
        M[i+1] = M[i] - 1
        if mini > M[i+1]:
            mini = deepcopy(M[i+1])

print(mini)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Grand Contest 023
Author     : Kitaura Hiromi
LastUpdate : 20180502
Since      : 20180428
"""
N = int(input())
A = list(map(int, input().split(" ")))

# O(NlogN)
S = []
for i in range(N+1):
    S.append(sum(A[:i]))
S = sorted(S)
cnt = 1
ret = 0
tmp = S[0]
for i in range(1, len(S)):
    if tmp == S[i]:
        cnt += 1
    else:
        ret += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = S[i]
ret += cnt * (cnt - 1) // 2
print(ret)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Grand Contest 023
Author     : Kitaura Hiromi
LastUpdate : 20180502
Since      : 20180428
"""
N = int(input())
A = list(map(int, input().split(" ")))

# O(NlogN)
S = []
tmp = 0
for i in range(N):
    S.append(tmp)
    tmp += A[i]
S.append(tmp)
S = sorted(S)
cnt = 1
ret = 0
tmp = S[0]
for i in range(1, len(S)):
    if tmp == S[i]:
        cnt += 1
    else:
        ret += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = S[i]
ret += cnt * (cnt - 1) // 2
print(ret)
### BUGGY CODE ###

k, s = list(map(int, input().split()))
cnt = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            total = i+j+k
            if total==s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = list(map(int, input().split()))
cnt = 0
for i in range(k+1):
    if i>s:
        break
    for j in range(k+1):
        if i+j>s:
            break
        if i+j+k>=s:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input()) 
A = [int(input()) for i in range(N)] 
for i in range(N):
  A[i] = A[i] - 200000
  print(max(A))
  A[i] = A[i] + 200000

### FIXED CODE ###

import numpy as np
N = int(input()) 
A = [int(input()) for i in range(N)]
a = max(A)
b = np.argmax(A)
A[b] = 0
c = max(A)
for i in range(N):
  if i != b:
    print(a)
  else:
    print(c)
### BUGGY CODE ###

N,K = map(int,input().split())
max_note = [0]*N
head = []
remain = []
for i in range(N):
    t,d = map(int,input().split())
    t -= 1
    remain.append(d)
    if d > max_note[t]:
        max_note[t] = d
for e in max_note:
    if e == 0:
        continue
    head.append(e)
    remain.remove(e)

head.sort()
head.reverse()
remain.sort()
remain.reverse()

ans = -float("inf")
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
note = [list(map(int,input().split())) for i in range(N)]
note = sorted(note,key=lambda x:(x[0],-x[1]))
cnt = 0
head = []
remain = []
for i in range(N):
    if note[i][0] > cnt:
        cnt = note[i][0]
        head.append(note[i][1])
    else:
        remain.append(note[i][1])
head = sorted(head,reverse = True)
remain = sorted(remain,reverse = True)
ans = 0
acc_head = [0]
acc_remain = [0]
tmp_head = 0
tmp_remain = 0
for i in range(len(head)):
    tmp_head += head[i]
    acc_head.append(tmp_head)
for i in range(len(remain)):
    tmp_remain += remain[i]
    acc_remain.append(tmp_remain)
for i in range(max(0,K-len(remain)),min(K,len(head))+1):
    deli = acc_head[i] + acc_remain[K-i]
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)
### BUGGY CODE ###

num = int(input())
words = []
answer = 0

for i in range(num):
  words.append(sorted(list(input())))
words.sort(key=lambda x:x[0])
for i in range(num):
  q = 0
  for j in range(num -i - 1):
    p = 0
    out = 0
    if q >0 and words[i][0] != words[j + 1 + i][0]:
      break
    for k in range(10):
      if words[i][k] == words[j + 1 + i][k]:
        p += 1
      else:
        break
    if p == 10:
      answer += 1
      q += 1
    
print(answer)

### FIXED CODE ###

import math
num = int(input())
words = {}

for i in range(num):
  a = str(sorted(list(input())))
  
  if a in words:
    words[a] += 1
  else:
  	words[a] = 1

points = list(words.values())
sum = 0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(len(points)):
  if points[i] > 1:
  	sum += combinations_count(points[i], 2)
print(sum)
### BUGGY CODE ###

from itertools import combinations
_, s = input(), input()
a = set()
for c in combinations(s, 3):
  a.add(c)
print(len(a))

### FIXED CODE ###

_, s = input(), input()
cnt = 0
for i in range(1000):
    t = "{:0>3}".format(i)
    ss = s
    if t[0] not in ss:
        continue
    ss = ss[ss.index(t[0]) + 1:]
    if t[1] not in ss:
        continue
    ss = ss[ss.index(t[1]) + 1:]
    if t[2] not in ss:
        continue
    cnt += 1
print(cnt)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def rec(cur):
    if len(cur) == 1:
        return cur[0]
    nxt = []
    for i in range(len(cur)-1):
        nxt.append(abs(cur[i] - cur[i+1]))
    return rec(nxt)

N = INT()
A = [a-1 for a in list(map(int, input()))]

ans = rec(A)
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lucas(n, k):
    return (n&k) == k

N = INT()
A = [a-1 for a in list(map(int, input()))]

def check(A):
    mod2 = 0
    for i, a in enumerate(A):
        if a == 1:
            mod2 += lucas(N-1, i)
            mod2 %= 2
    return mod2

res = check(A)
if res == 1:
    print(1)
    exit()

if A.count(1):
    print(0)
    exit()

A = [a//2 for a in A]
res = check(A)
if res == 1:
    print(2)
else:
    print(0)
### BUGGY CODE ###

from collections import defaultdict
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
h =defaultdict(int)
b = [0]*(n+1)
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i]+a[i]
    b[i+1] = (s[i+1]-i-1)%k
ddprint(s)
ddprint(b)
acc = 0
for i in range(n+1):
    if i>=k:
        h[b[i-k]] -= 1
    acc += h[b[i]]
    h[b[i]] += 1
    ddprint("i {} acc {} h {}".format(i,acc,h))
print(acc)


### FIXED CODE ###

from collections import defaultdict
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
h =defaultdict(int)
b = [0]*(n+1)
s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i]+a[i]
    b[i+1] = (s[i+1]-i-1)%k
ddprint(s)
ddprint(b)
acc = 0
for i in range(n+1):
    if i>=k:
        h[b[i-k]] -= 1
    acc += h[b[i]]
    h[b[i]] += 1
    #ddprint("i {} acc {} h {}".format(i,acc,h))
print(acc)
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))

data=[n+1]
for i in range(n):
  res=min(data)
  if res>p[i]:
    data.append(p[i])
print(len(data)-1)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in p:
  if i <= p[0]:
    p[0] = i
    ans += 1
print(ans)
### BUGGY CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

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

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

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (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[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)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)

main()


### 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 ###

#!/usr/bin/env python3
import sys


def solve(N: int, L: "List[int]"):
    L.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            from bisect import bisect_left, bisect_right
            k = bisect_left(L, L[i]+L[j])
            ans += (k-j-1)

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

from bisect import bisect_left, bisect_right



def solve(N: int, L: "List[int]"):
    ans = 0
    L.sort()

    for x in range(N):
        for y in range(x+1,N):
            ze = bisect_left(L, L[x]+L[y])            
            ans += (ze-y-1)
            
    print(ans)

    return
 


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

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

N = int(input())
s = []

for _ in range(N):
  a = str(input())
  alist = list(a)
  s.append(sorted(alist))
  
cnt = 0
while len(s) > 1:
  same = 0
  s1 = s.pop()
  same = s.count(s1)
  if same != 0:
    cnt += (same+1) * same / 2
    while s1 in s:
      s.remove(s1)

print(int(cnt))






### FIXED CODE ###

from collections import Counter
N = int(input())
s = []
cnt = 0
for _ in range(N):
  a = str(input())
  alist = sorted(list(a))
  s.append(str(''.join(alist)))
  
l = Counter(s)
for i in l.values():
  if i > 1:
    cnt += (i - 1) * i / 2
print(int(cnt))