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

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
    flag=0
    if i<len(a):
        j=i+1
        while j <len(a):
            if a[j]==a[i]:
                flag=1
            if a[j]%a[i]==0:
                a.pop(j)
            else:
                j+=1
        if flag==0:
            ans+=1
                
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=list()
for i in range(10**6+1):
    b.append(0)
for i in range(n):
    if b[a[i]]==0:
        j=1
        while j*a[i]<=10**6:
            b[j*a[i]]=1
            j+=1
        if (i==n-1 or a[i+1]!=a[i]):
            ans+=1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    goukei=0
    l=[0]
    i=0
    while i<m-1:
        goukei+=x[i+1]-x[i]
        l.append(x[i+1]-x[i])
        i+=1
    i=0
    while i<n-1:
        goukei-=max(l)
        l.remove(max(l))
        i+=1
    print(goukei)

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    x.sort()
    goukei=0
    l=[0]
    for i in range(m-1):
        goukei+=x[i+1]-x[i]
        l.append(x[i+1]-x[i])
    i=0
    l.sort()
    for i in range(n-1):
        goukei-=l[-1-i]
    print(goukei)
### BUGGY CODE ###

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

p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = sorted(list(map(int,input().split())), reverse=True)

for i in r:
    p_min = p[0]
    q_min = q[0]

    if p_min > i and q_min > i:
        break

    p_min_diff = i - p_min
    q_min_diff = i - q_min

    if p_min_diff >= q_min_diff and p_min_diff > 0:
        del p[0]
        p.extend([i])
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        del q[0]
        q.extend([i])

print(sum(p) + sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
N,Q = map(int,input().split())
tree = [[] for _ in range(N)]
cnt = [0]*N
for _ in range(N-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p,x = map(int,input().split())
    cnt[p-1] += x
sys.setrecursionlimit(10 ** 6)
def dfs(cur,parent):
    li = tree[cur]
    for chi in li:
        if chi == parent:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi,cur)
dfs(0,-1)
print(" ".join(map(str,cnt)))


### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
N,Q = map(int,input().split())
tree = [[] for _ in range(N)]
cnt = [0]*N
for _ in range(N-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p,x = map(int,input().split())
    cnt[p-1] += x
sys.setrecursionlimit(10 ** 6)
def dfs(cur,parent):
    li = tree[cur]
    for chi in li:
        if chi == parent:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi,cur)
dfs(0,-1)
print(" ".join(map(str,cnt)))
### BUGGY CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))

ans=1
for i in range(n):
    ans*=a[i]
    if (ans>10**18):
        ans=-1

if (ans>=0):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)

ans=1
for i in range(n):
    ans*=a[i]
    if (ans==0):
        break
    if (ans>10**18):
        ans=-1
        break

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

n, m = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	p, y = map(int, input().split())
	a.append([p,y])
	b[p-1].append(y)
dic = {}
for i in range(n):
	b[i].sort()
	for j,k in enumerate(b[i]):
		dic[k] = j+1

for i, j in a:
	x = b[i-1].index(j)
	print ("{:06d}".format(i) + "{:06d}".format(dic[j]))

### FIXED CODE ###

n, m = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	p, y = map(int, input().split())
	a.append([p,y])
	b[p-1].append(y)
dic = {}
for i in range(n):
	b[i].sort()
	for j,k in enumerate(b[i]):
		dic[k] = j+1

for i, j in a:
	print ("{:06d}".format(i) + "{:06d}".format(dic[j]))
### BUGGY CODE ###

s = str(input())
q = int(input())
Q = []
for i in range(q):
    query = list(map(str, input().split()))
    Q.append(query)

for query in Q:
    if query[0] == '1':
        s = s[::-1]
    elif query[0] == '2':
        if query[1] == '1':
            s = query[2] + s
        else:
            s = s + query[2]
print(s)

### FIXED CODE ###

from collections import deque

s = str(input())
q = int(input())
flip = -1
strf = deque()
strb = deque()

for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        flip = flip * -1
    elif query[0] == '2':
        if query[1] == '1':
            if flip == -1:
                strf.appendleft(query[2])
            else:
                strb.append(query[2])
        elif query[1] == '2':
            if flip == -1:
                strb.append(query[2])
            else:
                strf.appendleft(query[2])

# print(strf)
# print(strb)
ans = ''.join(strf) + s + ''.join(strb)
if flip == 1:
    ans = ans[::-1]
print(ans)

# s = str(input())
# q = int(input())
# flip = -1
# strs = '/'
 
# for i in range(q):
#     query = list(map(str, input().split()))
#     if query[0] == '1':
#         flip = flip * -1
#     elif query[0] == '2':
#         if query[1] == '1':
#             if flip == -1:
#                 strs = query[2] + strs
#             else:
#                 strs = strs + query[2]
#         else:
#             if flip == -1:
#                 strs = strs + query[2]
#             else:
#                 strs = query[2] + strs
 
# if flip == -1:
#     ans = strs.replace('/', s)
# else:
#     ans = strs[::-1].replace('/', s[::-1])
 
# print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())
L = sorted([int(s) for s in input().split()])

MAX_SEARCH = max(L) + 1


def check_search(middle, idx_short2, l_lng, l_lows):
    return l_lows[middle] + l_lows[idx_short2] > l_lng


l_lows = L[:2]
triangles = 0


for l_lng in L[2:]:
    for idx, l_low in enumerate(l_lows):
        left = 0
        right = len(l_lows) - 1 - idx
        end = right
        while (left < right):
            middle = (left + right) // 2
            if check_search(middle, len(l_lows) - 1 - idx, l_lng, l_lows):
                right = middle
            else:
                left = middle + 1
        triangles += (end - right)
    l_lows.append(l_lng)

print(triangles)


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
L = sorted([int(s) for s in input().split()])


def check_search(middle, idx_short2, l_lng, l_lows):
    return l_lows[middle] + l_lows[idx_short2] > l_lng


l_lows = L[:2]
triangles = 0


for l_lng in L[2:]:
    for idx, l_low in enumerate(l_lows):
        left = 0
        right = len(l_lows) - 1 - idx
        end = right
        while (left < right):
            middle = (left + right) // 2
            if check_search(middle, len(l_lows) - 1 - idx, l_lng, l_lows):
                right = middle
            else:
                left = middle + 1
        triangles += (end - right)
    l_lows.append(l_lng)

print(triangles)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
N = int(input())
S = input().rstrip()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] != S[y]and S[y] != S[z] and S[x] != S[z]:
            ans = ans-1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)
### BUGGY CODE ###

n=int(input())
v=[int(i) for i in input().split()]
v_even=[vi for vi in v[::2]]
v_odd=[vi for vi in v[1::2]]
def same(v):
    count=[]
    v_set=set(v)
    for vi in v_set:
        count.append([vi, v.count(vi)])
    count=sorted(count, key = lambda k:k[1])
    return count
e1=len(v_even)-same(v_even)[-1][1]
o1=len(v_odd)-same(v_odd)[-1][1]
e2=len(v_even)-same(v_even)[-2][1] if len(set(v_even))>1 else len(v_even)
o2=len(v_odd)-same(v_odd)[-2][1] if len(set(v_odd))>1 else len(v_odd)
if same(v_even)[-1][0]==same(v_odd)[-1][0]:
    print(min(e1+o2, e2+o1))
else:
    print(e1+o1)

### FIXED CODE ###

from collections import Counter
n=int(input())
v=list(map(int, input().split()))
v1=Counter(v[::2])
v2=Counter(v[1::2])
c1=v1.most_common()+[(0, 0)]
c2=v2.most_common()+[(0, 0)]
if c1[0][0]==c2[0][0]:
    ans=max(c1[1][1]+c2[0][1], c1[0][1]+c2[1][1])
    print(n-ans)
else:
    print(n-c1[0][1]-c2[0][1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
mod = 1000000007

for i in range(N):
    for j in range(i+1,N):
        ans += A[i]*A[j]
        ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
mod = 1000000007

a = sum(A)

for i in range(N):
    a -= A[i]
    ans += A[i]*a
    ans %= mod

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

X,Y,Z,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A,reverse=True)
B = sorted(B,reverse=True)
C = sorted(C,reverse=True)
#print(A,B,C)

list1 = []
a,b,c = 0,0,0

for a in range(X):
  for b in range(Y):
    for c in range(Z):
      list1.append(A[a]+B[b]+C[c])

for i in range(K):
  print(max(list1))
  list1.remove(max(list1))

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [0] * (X * Y)
for i in range(X):
  for j in range(Y):
    AB[i * Y + j] = A[i] + B[j]

AB = sorted(AB, reverse = True)[:K]
#print(AB)
ABC = []
for i in range(len(AB)):
  for j in range(Z):
    ABC.append(AB[i] + C[j])
    
ABC = sorted(ABC, reverse = True)[:K]

for i in range(K):
  print(ABC[i])
### BUGGY CODE ###

m,n=map(int,input().split())
print(m**n%1000000007)


### FIXED CODE ###

m,n=[ int(x) for x in input().split()]    
k=1000000007

REM={}

def remainder(i):

    if i in REM.keys():
        return REM[i]

    if i==1:
        re=m%k
        REM[1]=re     
        return re

    if i==2:
        re=(m%k)**2%k
        REM[2]=re        
        return re
    
    left=i//2
    right=i-left
    REM[i]=remainder(left)*remainder(right)%k
    return REM[i]


print(remainder(n))
### BUGGY CODE ###

import time
import numpy as np
import copy

tflag = True
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = np.random.randint(m,size=(N))
  st = time.time()
else:
  a = map(int,raw_input().split())
  N = a[0]
  x = a[1]
  A = map(int,raw_input().split())

B = copy.deepcopy(A)
m = sum(B)
for idx in xrange(1,N):
  A = np.append(A, A[0])
  A = np.delete(A, 0)
  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)

### FIXED CODE ###

import time
import numpy as np
import copy

tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = list(np.random.randint(m,size=(N)))
  st = time.time()
else:
  N, x = map(int,raw_input().split())
  A = map(int,raw_input().split())

#B = copy.deepcopy(A)
B = A
A = A + A
m = sum(B)
for idx in xrange(1,N):
  for jdx in xrange(N):
    if B[jdx] > A[jdx+N-idx]:
      B[jdx] = A[jdx+N-idx]
#  A = np.append(A, A[0])
#  A = np.delete(A, 0)
#  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
L=[]
for i in range(min(3002,len(A))):
    for j in range(min(3002,len(B))):
        for k in range(min(3002,len(C))):
            L.append(A[i]+B[j]+C[k])
L.sort(reverse=True)
for p in range(K):
    print(L[p])

### FIXED CODE ###

import heapq
def hq(x,y,z):
    return (-A[x-1]-B[y-1]-C[z-1],x,y,z)
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

visited=[hq(1,1,1)]
q=[]
heapq.heappush(q,hq(1,1,1))
for _ in range(K):
    e,x,y,z=heapq.heappop(q)
    if x+1<=X and hq(x+1,y,z) not in visited:
        heapq.heappush(q,hq(x+1,y,z))
        visited.append(hq(x+1,y,z))
    if y+1<=Y and hq(x,y+1,z) not in visited:
        heapq.heappush(q,hq(x,y+1,z))
        visited.append(hq(x, y+1, z))
    if z+1<=Z and hq(x,y,z+1) not in visited:
        heapq.heappush(q,hq(x,y,z+1))
        visited.append(hq(x, y, z+1))
visited.sort()
for i in visited[0:K]:
    print(-i[0])
### BUGGY CODE ###

N, K = list(map(int, input().split()))
hList = list(map(int, input().split()))

dp = [float("inf")] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K + 1):
        if j > i:
            break
        dp[i] = min(dp[i - j] + abs(hList[i] - hList[i - j]), dp[i])

print(dp[N - 1])


### FIXED CODE ###

N, K = list(map(int, input().split()))
hList = list(map(int, input().split()))

dp = [float("inf")] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K + 1):
        if j > i:
            break
        dp[i] = min(dp[i - j] + abs(hList[i] - hList[i - j]), dp[i])

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

n,q = map(int, input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    ans.append(s[l-1:r].count('AC'))
print(*ans,sep='\n')

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
a = [0]*2
for i in range(2,n+1):
    a += [a[i-1]+s[i-2:i].count('AC')]
ans = []
for _ in range(q):
    l,r = map(int,input().split())
    ans.append(a[r]-a[l])
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
N=int(sys.stdin.readline())
L=list(map(int,sys.stdin.readline().split()))
C=list(set(L))
x=0
for i in range(len(C)):
  x += int((L.count(C[i]))*(L.count(C[i])-1)/2)  
for K in range(N):
  print(x-L.count(L[K])+1)

### FIXED CODE ###

import sys
from collections import Counter
N=int(sys.stdin.readline())
L=list(map(int,sys.stdin.readline().split()))
C=Counter(L)
x=0
for a in C.values():
  x += int(a*(a-1)/2)  
for K in range(N):
  print(x-C[L[K]]+1)
### BUGGY CODE ###

n,a,b,c,d,e=[int(input()) for i in range(6)]
dist=[n,0,0,0,0,0]
move=[a,b,c,d,e,0]
t=0
while dist[5]<n:
  dist_t=[max(0,dist[0]-move[0])]
  for j in range(1,6):
    dist_t.append(max(0,dist[j]-move[j])+min(dist[j-1],move[j-1]))
  t=t+1
  dist=dist_t
print(t)
    


### FIXED CODE ###

n=int(input())
A=[int(input()) for i in range(5)]
print(5+(n-1)//min(A))
### BUGGY CODE ###

from functools import reduce
n, *a = map(int, open(0).read().split())
ans = reduce(lambda x, y: x*y, a, 1)
print((-1 if ans > 10**18 else ans))


### FIXED CODE ###

n, *a = map(int, open(0).read().split())
ans = 1
for i in range(n):
    if ans == -1:
        if a[i] == 0:
            ans = 0
            break
    else:
        ans *= a[i]
        if ans > 10**18:
            ans = -1
print(ans)
### BUGGY CODE ###

#python 3.5.2

N, M = [int(i) for i in input().split()]
As = [int(i) for i in input().split()]
BCs = [[int(j) for j in input().split()] for i in range(M)]

#LRs = list(map(list, zip(*LRs)))  # 転置

choiced = [bc[1] for bc in BCs for i in range(bc[0])]
choiced = choiced + As
choiced = sorted(choiced)[::-1]
print(sum(choiced[:N]))

### FIXED CODE ###

#python 3.5.2

N, M = [int(i) for i in input().split()]
As = [int(i) for i in input().split()]
BCs = [[int(j) for j in input().split()] for i in range(M)]
BCs += [[1, a] for a in As]
BCs = sorted(BCs, key=lambda x: x[1], reverse=True)
cnt = 0
sum = 0
for b, c in BCs:
    if N < cnt + b:
        sum += (N - cnt)*c
        break
    else:
        sum += b*c
        cnt += b
print(sum)
### BUGGY CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				reached.remove(k)
				q.append(k)

for i in range(m):
	a,b = map(int, input().split())
	g[a].append(b)
	g[b].append(a)

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

### FIXED CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

for i in range(m):
	a,b = map(int, input().split())
	g[a].append(b)
	g[b].append(a)

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")
### BUGGY CODE ###

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = []  # O(N)で回した連続値のmod(2019)の値
for i in range(len(s)):
    mod = int(s[i:]) % 2019
    lst_mod.append(mod)
    if mod == 0:
        ans = + 1

count = list(collections.Counter(lst_mod).values())
for i in range(len(count)):
    if count[i] == 1:
        continue
    ans += comb(count[i])
print(int(ans))


### FIXED CODE ###

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = [0]*2019  # O(N)で回した連続値のmod(2019)の値
lst_mod[0] += 1
num, dim = 0, 1
for char in reversed(s):
    num += int(char)*dim
    num %= 2019
    dim *= 10
    dim %= 2019  # サイズを大きくしたくないからmod(2019)を使う
    lst_mod[num] += 1

for mod in lst_mod:
    ans += comb(mod)
print(int(ans))
### BUGGY CODE ###

def main():
    s = input()
    l = [0 for _ in range(len(s))]
    for i in range(1, len(s) + 1):
        x = int(s[-i:])
        l[-i] = x % 2019
    ans = 0
    for i in range(4, len(s) + 1, 1):
        for j in range(0, i - 3, 1):
            if j == 0:
                x = int(s[-i:]) % 2019
            else:
                x = int(s[-i:]) - int(s[-j:])
            if x % 2019 == 0:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


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

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]


def bfs(x, y):
    queue = deque([(x, y, 0)])
    visited = [[False]*W for _ in range(H)]

    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited[py][px] = True
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and not visited[cy][cx] and maze[cy][cx] == ".":
                queue.append((cx, cy, cost + 1))
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == ".":
            ans = max(ans, bfs(x, y))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

import sys, numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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

adjm = [[float('inf')] * N for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjm[a][b] = 1
    adjm[b][a] = 1
    
dv = dijkstra(adjm, indices=v-1)
du = dijkstra(adjm, indices=u-1)
dOK = [(i>j)*i for i, j in zip(dv, du)]

print(int(max(dOK)-1))

### FIXED CODE ###

import sys, heapq
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N, u, v = map(int, input().split())



def dijkstra_heap(s,edge):
#始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

adjl = [[] for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjl[a].append([1, b])
    adjl[b].append([1, a])

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))