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

'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    q = int(ipt())
    for _ in range(q):
        a,b = map(int,ipt().split())
        if a > b:
            a,b = b,a
        ans = a-1
        tgt = a*b
        a += 1
        for i in range(b-1,0,-1):
            if i*a < tgt:
                ans += 1
                a += 1
            if i**2 < tgt:
                ans += i-1
                break
        print(ans)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    q = int(ipt())
    for _ in range(q):
        a,b = map(int,ipt().split())
        if a > b:
            a,b = b,a
        tgt = a*b
        rt = int(tgt**0.5+0.0000000000001)
        ans = rt*2-1
        if a == b:
            ans -= 1
        elif rt**2 == tgt:
            ans -= 2
        elif rt*(rt+1) < tgt:
            pass
        elif rt**2-1 < tgt:
            ans -= 1
        print(ans)

    return None

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

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

sum_s = [[], []]

for y in range(H):
	count, line = 0, []
	for x in range(W):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[0] += [line]

for x in range(W):
	count, line = 0, []
	for y in range(H):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[1] += [line]
"""
for line in sum_s[0]:
	print(*line)
print()
for line in sum_s[1]:
	print(*line)
"""
max_score = 0
for y in range(H):
	for x in range(W):
		max_score = max(max_score, sum_s[0][y][x] + sum_s[1][x][y] - 1)

print(max_score)


### FIXED CODE ###

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

sum_s = [[], []]

for y in range(H):
	count, line = 0, []
	for x in range(W):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[0] += [line]

for x in range(W):
	count, line = 0, []
	for y in range(H):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[1] += [line]
"""
for line in sum_s[0]:
	print(*line)
print()
for line in sum_s[1]:
	print(*line)
"""
max_score = 0
for y in range(H):
	for x in range(W):
		max_score = max(max_score, sum_s[0][y][x] + sum_s[1][x][y] - 1)

print(max_score)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ac = []
for i in range(n-1):
  if s[i:i+2] == "AC":
    ac.append(1)
  else:
    ac.append(0)
for j in range(q):
  l,r = map(int, input().split())
  if r == q:
    r -= 1
  ls = ac[l-1:r-1]
  print(ls.count(1))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac = [0] * (n+1)
for i in range(n):
  if s[i:i+2] == "AC":
    ac[i+1] = ac[i] + 1
  else:
    ac[i+1] = ac[i]
for j in range(q):
  l,r = map(int, input().split())
  print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

import numpy as np

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = np.zeros((h,w),dtype="int")
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1
 
l = 6600
m = 0
 
M = np.zeros((h,w,l),dtype="int")
N = np.zeros((h,w),dtype="int")
N[0][0] = C[0][0]
 
s = 0
Q = [[0, 0]]
 
M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1
 
while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        V[i+1][j] -= 1
        # print(N[i+1][j], N[i][j] + C[i+1][j])
        N[i+1][j] = max(N[i+1][j], N[i][j] + C[i+1][j])
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1
        V[i][j+1] -= 1
        N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1
 
# print(M[-1][-1])
 
ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
s=[]
for i in range(N-1):
    if A[i] not in s:
        print(A.count(i+1))
        s.append(i)
    else:
        print(0)
print(0)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
P=[0]*N
for i in range(N-1):
    P[A[i]-1]+=1
for i in range(N):
    print(P[i])
### BUGGY CODE ###

H,W,N = map(int,input().split())
if N == 0:
  print((H-2)*(W-2))
  for i in range(9):
    print(0)
  exit()

AB = [list(map(int,input().split())) for _ in range(N)]

Board = [[0 for _ in range(W)] for _ in range(H)]
Cell = []
Count = [0 for _ in range(10)]

for a,b in AB:
  a -= 1
  b -= 1
  Board[a][b] = 1
  for i in range(-1,2):
    for j in range(-1,2):
      if 1 <= a+i <= H-2 and 1 <= b+j <= W-2:
        Cell.append([a+i,b+j])
Cell.sort(key=lambda x:(x[0],x[1]))
#print(Board)
#print(Cell)
prea = 0
preb = 0
for a,b in Cell:
  if a == prea and b == preb:
    continue
  c = 0
  for k in range(-1,2):
    for l in range(-1,2):
      c += Board[a+k][b+l]
  Count[c] += 1
  prea = a
  preb = b

Count[0] = (H-2)*(W-2)-sum(Count[1:])
for c in Count:
  print(c)

### FIXED CODE ###

from collections import defaultdict

H,W,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

Cells = defaultdict(int)
Count = [(H-2)*(W-2)] + [0 for _ in range(9)]

for a,b in AB:
  a -= 1
  b -= 1
  for i in range(-1,2):
    for j in range(-1,2):
      if 1 <= a+i <= H-2 and 1 <= b+j <= W-2:
        Count[Cells[(a+i,b+j)]] -= 1
        Count[Cells[(a+i,b+j)]+1] += 1
      Cells[(a+i,b+j)] += 1
for c in Count:
  print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,k = map(int, input().split(' '))
prices = []
for i in range(n):
    prices.append(int(input()))

sortedPrices = sorted(prices)


trees = []
for i in range(k):
    trees.append(sortedPrices.pop(0))

hdiff = 1000000000

while(True):
    hdiff = min( (trees[-1] - trees[0]), hdiff )
    trees.pop(0)
    if len(sortedPrices) == 0:
        break
    trees.append(sortedPrices.pop(0))

print(hdiff)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split(' '));
h = [int(input()) for i in range(N)]
h.sort()
print( min( h[i+K-1] - h[i] for i in range(N-K+1) ) )
### BUGGY CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
mn = min(ls)
for i in range(m):
    if di[i][1] > mn:
        ls += [di[i][1]]*di[i][0]
ls.sort()
ls = ls[n*(-1):]
print(sum(ls))

### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
fi = []
for i,j in di:
    fi.append([j,i])
for k in ls:
    fi.append([k,1])
fi.sort(reverse=True)
ans = 0
cnt = 0
how = 0
while True:
    if how + fi[cnt][1] < n:
        how += fi[cnt][1]
        ans += fi[cnt][1]*fi[cnt][0]
    else:
        ans += (n-how)*fi[cnt][0]
        break
    cnt += 1
print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
c=0
while a>1 or b>1:
  if (a-2)>1 or (b-2)>1:
    a=a-2
    b=b-2
    c=c+1
print(c)  


### FIXED CODE ###

a,b=map(int,input().split())
c=0
d=a*(a-1)//2
e=b*(b-1)//2
while d>0:
  d=d-1
  c=c+1
while e>0:
  e=e-1
  c=c+1
print(c)
### BUGGY CODE ###

# 初期入力
N = int(input())
S =input()
S_list =[i for i in S]

#
keizoku =True
count_list =[0,1]
for i in range(N):
    for j in range(len(S)-1):
        if S[j] == S[j+1]:
            del S_list[j]
            S="".join(S_list)
            break
print(len(S))

### FIXED CODE ###

# 初期入力
N = int(input())
S =input()
S_list =[i for i in S]

#
S_2 =[]
S_2.append(S[0])
for i in range(N):
    for j in range(len(S)-1):
        if S[j] != S[j+1]:
            S_2.append(S[j+1])
    S="".join(S_2)
    break
print(len(S))
### BUGGY CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])
### BUGGY CODE ###

n, p = map(int, input().split(" "))
s = int(input())

divider = pow(10, n-1)
minus = s // divider * divider
r = n*(n+1)//2
count = 0
for i in range(r):
    if (s // divider) % p == 0:
        count += 1
    divider //= 10
    if divider == 0:
        n -= 1
        divider = pow(10, n-1)
        s -= minus
        minus = s // divider * divider

print(count)

### FIXED CODE ###

from collections import Counter

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

ans = 0
if 10 % p == 0: # p = 2, 5
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

s = s[::-1]
power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

counter = Counter(t)
for i in counter.values():
    ans += i * (i-1) // 2
ans += counter[0]
print(ans)

# count = [0] * p
# count[0] = 1
# for i in t:
#     ans += count[i]
#     count[i] += 1
# print(ans)
### BUGGY CODE ###

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

ans = 1
for x in l:
    if x == 0:
        ans = 0
        break
    ans = ans * x

if ans > 1000000000000000000:
    ans = -1

print(ans)


### FIXED CODE ###

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

import sys
if l.count(0) > 0:
    print(0)
    sys.exit()

ans = 1
for x in l:

    ans = ans * x

    if ans > 1000000000000000000:
        print(-1)
        sys.exit()

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

from fractions import gcd
k=int(input())
s=0
for i in range(1,k+1):
    for j in range(1, k+1):
        tmp=gcd(i,j)
        for h in range(1, k+1):
            s+=gcd(tmp,h)
print(s)

### FIXED CODE ###

import math
k=int(input())
s=0
for i in range(1,k+1):
    for j in range(1, k+1):
        tmp=math.gcd(i,j)
        for h in range(1, k+1):
            s+=math.gcd(tmp,h)
print(s)
### BUGGY CODE ###

import collections

N = int(input())

a = list()

for i in range(N):
    S = input()
    a.append(S)

c = collections.Counter(a)

#print(c.most_common()[0][1])

b =list()
max = 0

if(N == len(c)):
    b = list(set(a))
    b.sort()
    for i in range(len(b)):
        print(b[i])
else:
    for i in range(len(c)):
        if (int(c.most_common()[0][1]) == int(c.most_common()[i][1]) and max <= int(c.most_common()[i][1])):
            b.append(c.most_common()[i][0])
            max = c.most_common()[i][1]

    b.sort()

    for i in range(len(b)):
        print(b[i])


### FIXED CODE ###

from collections import*
_,*s=open(0)
c=Counter(s).most_common()
print(*sorted(a*(b==c[0][1])for a,b in c))
### BUGGY CODE ###

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

result = 0
for a in range(N):
    for b in range(a+1, N):
        for c in range(b+1, N):
            if arr[c] >= arr[a]+arr[b]:
                break
            result += 1

print(result)


### FIXED CODE ###

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

memo = [0]*1001
for x in range(1001):
    for i in arr:
        if i < x:
            memo[x] += 1

result = 0
for a in range(N):
    for b in range(a+1, N):
        aa = arr[a]
        bb = arr[b]
        if aa+bb > 1000:
            result += N-b-1
        else:
            result += memo[aa+bb]-b-1

print(result)
### BUGGY CODE ###

number = int(input())
# values = [i+2 for i in range(2*10**5)]
values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 1:
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)


### FIXED CODE ###

number = int(input())
# values = [i+2 for i in range(2*10**5)]
values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 0:
        dp[a] = dp[a] + 1
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)
### BUGGY CODE ###



N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans *= now
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans *= now

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

fac = 1
for i in range(N):

    i += 1
    fac = (fac * i) % (10 ** 9 + 7)

print ((fac * ans) % (10 ** 9 + 7) )

### FIXED CODE ###



N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans = (ans * now) % (10 ** 9 + 7)
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans = (ans * now) % (10 ** 9 + 7)

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

fac = 1
for i in range(N):

    i += 1
    fac = (fac * i) % (10 ** 9 + 7)

print ((fac * ans) % (10 ** 9 + 7) )
### BUGGY CODE ###

N = int(input())
L = list(input())
ANS = []
L = ["-"] + L + ["-"]
for i in range(1,N+1) :
    p = L[(i+1):].count("E")
    q = L[:i].count("W")
    ANS.append(p+q)
print(min(ANS))


### FIXED CODE ###

N = int(input())
S = list(input())
ANS = []
ans = 0
for i in range(0,N) :
    if i == 0 :
        ans += S[1:].count("E")
        ANS.append(ans)
    elif S[i-1] == "E" and S[i] == "E" :
        ans -= 1
        ANS.append(ans)
    elif S[i-1] == "W" and S[i] == "W" :
        ans += 1
        ANS.append(ans)
print(min(ANS))
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
cnt = n * (n - 1) * (n - 2) / 6
jud = []

for i in range(n):
    for j in range(n):
        if i > j:
            jud.append(L[i] + L[j])

for m in range(n):
    for p in range(len(jud)):
        if L[m] >= jud[p]:
            cnt -= 1

if cnt < 0:
    print(0)
else:
    print(int(cnt))

### FIXED CODE ###

from _bisect import bisect_left
from _bisect import bisect_right

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

cnt = 0

for a in range(n):
    for b in range(n):
        if a < b:
            c = bisect_left(L, L[a] + L[b], b)
            cnt += c - b - 1
print(cnt)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    n = int(input())
    s = str(input())

    res = 0
    for i in range(1000):
        t = str(i).zfill(3)
        pos = 0
        for j in s:
            if t[pos] == j:
                pos += 1
            if pos == 3:
                res += 1
                break
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

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

def gcd(a, b):
  if (min(a, b) == 0):
    return max(a, b)
  elif (a > b):
    return gcd(b, a % b)
  else:
    return gcd(a, b % a)

gcd_forward = []
gcd_all = numbers[0]
for i in range(0, N - 1):
  gcd_all = gcd(gcd_all, numbers[i])
  gcd_forward.append(gcd_all)

gcd_backward = []
gcd_all = numbers[-1]
for i in range(N - 1, 0, -1):
  gcd_all = gcd(gcd_all, numbers[i])
  gcd_backward.insert(0, gcd_all)

gcd_forward.insert(0, gcd_backward[0])
gcd_backward.append(gcd_forward[-1])

gcd_max = 1
for i in range(N):
  gcd_max = max(gcd_max, gcd(gcd_forward[i], gcd_backward[i]))
  
print(gcd_max)


### FIXED CODE ###

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

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

gcd_forward = [numbers[0]]
for i in range(1, N - 1):
  gcd_all = gcd(gcd_forward[-1], numbers[i])
  gcd_forward.append(gcd_all)

gcd_backward = [numbers[-1]]
for i in range(N - 2, 0, -1):
  gcd_all = gcd(gcd_backward[-1], numbers[i])
  gcd_backward.append(gcd_all)

gcd_max = 1
for i in range(N):
  gcd_temp = 1
  if (i == 0):
    gcd_temp = gcd_backward[-1]
  elif (i == N - 1):
    gcd_temp = gcd_forward[-1]
  else:
    gcd_temp = gcd(gcd_forward[i - 1], gcd_backward[N - 2 - i])
  gcd_max = max(gcd_max, gcd_temp)
  
print(gcd_max)
### BUGGY CODE ###

s = input()
cnt = 0
ss = []
nums = [(i+1)*2019 for i in range(200000//2019) if not "0" in str((i+1)*2019)]
for start in range(len(s)):
  end = start + 3
  while(end+1<=len(s)):
    if int(s[start:end+1]) in nums:
      cnt += 1
    end += 1
print(cnt)

### FIXED CODE ###

s = input()
l = len(s)
dp = [0]*2019
dp[0] = 1
r = 0
for i in range(1, l + 1):
    r += int(s[-i]) * pow(10, i - 1, 2019)
    r %= 2019
    dp[r] += 1
    
print(sum([(i * (i - 1)) // 2 for i in dp]))
### BUGGY CODE ###

import collections

cnt = 0

N = int(input())
string_counters = [collections.Counter(input()) for i in range(N)]

cnt = 0
for i in range(len(string_counters)-1):
    pattern_i = string_counters[i]
    for j in range(i+1, len(string_counters)):
        pattern_j = string_counters[j]
        if pattern_i == pattern_j:
            cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
cnt = dict()
output = 0

for i in range(N):
    string = ''.join(sorted(input()))
    cnt.setdefault(string, 0)
    output += cnt[string]
    cnt[string] += 1

print(output)
### BUGGY CODE ###

L, R= (int(i) for i in input().split())  

_min = 2018

for g in range(R-L):
	_start = (L+g)*(L+g+1)
	for i in range(R-L-g):
		_min = min(_min, _start%2019)
		_start += L+g
	if g == 2019:
		break

print(_min)

### FIXED CODE ###

L, R= (int(i) for i in input().split())  

_min = 2018
_init = L%2019

for g in range(R-L):
	plus = _init + g
	_start = (plus*(plus+1))%2019
	for i in range(R-L-g):
		_min = min(_min, _start)
		_start += plus
		_start = _start%2019
		if _min == 0:
			break
	if g == 2019 or _min == 0:
		break

print(_min)
### BUGGY CODE ###

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

mydata = []

kazu = list(range(1,1001))
for i in p_L:

    kitai = sum(kazu[0:i])/i
    mydata.append(kitai)



res = [0] * (n+1)

res[0] = mydata[0]
for i in range(len(mydata)-1):
    res[i+1] = res[i] + mydata[i+1]

# print(mydata)
# print(res)
# print("----")
ans = 0
for i in range(n-k+1):
    ans = max(ans,sum(mydata[i:i+k]))
    #print(mydata[i:i+k])
print(ans)

### FIXED CODE ###

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

mydata = []

kazu = list(range(1,1001))
for i in p_L:

    kitai = sum(kazu[0:i])/i
    mydata.append(kitai)

res = [0] * (n+1)

res[0] = mydata[0]
for i in range(len(mydata)-1):
    res[i+1] = res[i] + mydata[i+1]

# print(mydata)
# print(res)
# print("----")
ans = 0
for i in range(n):
    tmp = res[i] - res[i-k]
    ans = max(ans,tmp)
    #print(mydata[i:i+k])
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ca = ord('a')
T = [ord(c) - ca for c in S]

ans = 0
nds = [[None]*26 for i in range(N**2)]
root = nds[0]
cs = [root]*N
gen = 0
for i in range(N):
    j = i
    cur = root
    while j < N and cur[T[j]] is not None:
        cur = cur[T[j]]
        j += 1
    ans = max(ans, j - i)
    e = T[i]
    for k in range(i):
        c = cs[k]
        if c[e] is None:
            cs[k] = c[e] = nds[gen]
            gen += 1
        else:
            cs[k] = c[e]
print(ans)

### FIXED CODE ###

def solve():
    N = int(input())
    S = input()

    base = 37
    def rolling_hash(s, mod):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    mod1 = 10**9 + 9; mod2 = 10**9 + 7
    h1, pw1 = rolling_hash(S, mod1)
    h2, pw2 = rolling_hash(S, mod2)

    def chk(l, h, pw, mod):
        p = pw[l]
        for i in range(min(l, N-2*l+1)):
            D[i] = (h[l+i] - h[i]*p) % mod
        s = set()
        for i in range(l, N-l+1):
            s.add(D[i-l])
            D[i] = v = (h[l+i] - h[i]*p) % mod
            if v in s:
                return 1
        return 0

    H = [set() for i in range(N//2+2)]
    D = [0]*N
    E = [0]*N
    k = N//2
    for l in range(1, N//2+1):
        if not chk(l, h1, pw1, mod1):
            k = l-1
            break
    ans = 0
    for l in range(k, 0, -1):
        if chk(l, h2, pw2, mod2):
            ans = l
            break
    print(ans)
solve()