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

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    heappush(Q,(0,point))
    
    while Q:
        c,p=heappop(Q)
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                heappush(Q,(c+1,np))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d.keys():
        d[b].append(a)
    else:
        d[b]=[a]
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")

### FIXED CODE ###

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
for i in range(m):
    a,b = v[i]
    q = deque()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))

print(ans)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

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

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

for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

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

ans = [0]*N
for i in A:
    ans[i-1]+=1
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j] = copy.deepcopy(NEX[i][k])
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()

### FIXED CODE ###

def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j].clear()
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()
### BUGGY CODE ###

L=list()
s=input()
K=int(input())
if len(s)<10:
  for i in range(len(s)):
    for j in range(i+1,len(s)+1):
      L.append(str(s[i:j]))
  L=sorted(list(set(L)))
  print(L[K-1])
else:
  A=sorted(list(s))
  B=[A[0],A[1],A[2],A[3],A[4]]
  for i in range(len(s)):
    if s[i] in B:
      for j in range(i+1,len(s)+1):
        L.append(str(s[i:j]))
      L=sorted(list(set(L)))
  print(L[K-1])

### FIXED CODE ###

L=list()
s=input()
K=int(input())
if len(s)<10:
  for i in range(len(s)):
    for j in range(i+1,len(s)+1):
      L.append(str(s[i:j]))
  L=sorted(list(set(L)))
  print(L[K-1])
else:
  A=sorted(list(s))
  B=[A[0],A[1],A[2],A[3],A[4]]
  for i in range(len(s)):
    if s[i] in B:
      for j in range(i+1,min(i+6,len(s)+1)):
        L.append(str(s[i:j]))
      L=sorted(list(set(L)))
      if len(L)>K:
        L=list(L[:K])
  print(L[K-1])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edge[a][b] = c
    edge[b][a] = c
Q,K = map(int,input().split())
cost = dijkstra(edge,indices=K)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x]+cost[y]))

### FIXED CODE ###

N = int(input())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1].append((c,b-1))
    graph[b-1].append((c,a-1))
Q,K = map(int,input().split())

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

cost = dijkstra(graph,N,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))
### BUGGY CODE ###

n=int(input())
a=input().split()

a_odd=list([int(a[i]) for i in range(n) if i%2==1])
a_even=list([int(a[i]) for i in range(n) if i%2==0])

def count_change(a_sublist, i):
    return len([num for num in a_sublist if num!=i])

temp=n
for i in set(a_odd):
    for j in set(a_even):
        if i!=j:
            c=count_change(a_odd,i)+count_change(a_even,j)
            if temp>c:
                temp=c

if temp==n:
    print(len(a_odd))
else:
    print(temp)

### FIXED CODE ###

import collections

n=int(input())
a=input().split()

a_odd=list([int(a[i]) for i in range(n) if i%2==1])
a_even=list([int(a[i]) for i in range(n) if i%2==0])

ca_odd=collections.Counter(a_odd)
ca_even=collections.Counter(a_even)

def count_change(a_sublist, i):
    return len([num for num in a_sublist if num!=i])

loop_set_a_odd=set ([i[0] for i in ca_odd.most_common()[0:min(len(ca_odd),2)]])
loop_set_a_even=set( [ i[0] for i in ca_even.most_common()[0:min(len(ca_even),2)]])

temp=n
for i in loop_set_a_odd:
    for j in loop_set_a_even:
        if i!=j:
            c=count_change(a_odd,i)+count_change(a_even,j)
            if temp>c:
                temp=c

if temp==n:
    print(len(a_odd))
else:
    print(temp)
### BUGGY CODE ###

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

ans = set(list(range(1, N + 1)))
for lr in LR:
    l, r = lr
    ans = ans & set(list(range(l, r + 1)))
print(len(list(ans)))


### FIXED CODE ###

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

A, B = 1, N
for lr in LR:
    L, R = lr
    if R < A or B < L:
        print(0)
        exit()

    if A <= L <= R <= B:
        A, B = L, R
    elif L <= A <= R <= B:
        B = R
    elif A <= L <= B <= R:
        A = L
print(B - A + 1)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])

MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


lcm = A[0]
for a in A[1:]:
    lcm = lcm * a // gcd(lcm, a)


MOD = 10 ** 9 + 7
lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

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

N, X, Y = [int(i) for i in input().split()]

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)

for k in range(1,N):
    print(p.count(k))    

### FIXED CODE ###

N, X, Y = [int(i) for i in input().split()]

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
    
import collections
c = collections.Counter(p)
for k in range(1,N):
    print(c[k])
### BUGGY CODE ###

n,m=map(int, input().split())
a=list(map(int,input().split())) 
b=[sum(a[0:i]) for i in range(1,n+1)]
c=[b[i]%m for i in range(n)]
ans=0
import collections
k=list(collections.Counter(c).items())
for x in k:
    j=True
    if x[0]==0:
        ans+=x[1]*(x[1]+1)//2
        j=False
    if x[1]>1 and j:
        ans+=(x[1]-1)*x[1]//2
print(ans)

### FIXED CODE ###

n,m=map(int, input().split())
a=list(map(int,input().split())) 
b=[a[0]]
for i in range(1,n):
    b.append(b[-1]+a[i])
c=[b[i]%m for i in range(n)]
ans=0
import collections
k=list(collections.Counter(c).items())
for x in k:
    j=True
    if x[0]==0:
        ans+=x[1]*(x[1]+1)//2
        j=False
    if x[1]>1 and j:
        ans+=(x[1]-1)*x[1]//2
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
p = [int(a) for a in input().split()]

max_index = 0
max_sum = 0
for i in range(n-k+1):
  t = sum(p[i:i+k])
  if max_sum < t:
    max_sum = t
    max_index = i

ans = 0
for j in range(max_index, max_index+k):
  su = p[j] * (p[j] + 1) / 2
  ans += su / p[j]
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
i = 0
kitaichi = [0] * n
kitaichi_sum = [0] * n
ans = 0
for p in input().split():
  kitaichi[i] = int(p) * (int(p)+1) / 2 / int(p)
  if i == 0:
    kitaichi_sum[i] = kitaichi[i]
  elif i >= k:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i] - kitaichi[i-k]
    if kitaichi_sum[i] > ans:
      ans = kitaichi_sum[i]
  else:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i]
  if kitaichi_sum[i] > ans:
    ans = kitaichi_sum[i]
  i += 1
print(ans)
### BUGGY CODE ###

import heapq
N,M = map(int, input().split())
E = [[] for _ in range(N)]
memo = [0]*N
for _ in range(N+M-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    memo[b-1] = 1

root = memo.index(0)
rnk = [0]*N
par = [-1]*N

h = [root]
while h:
    temp = heapq.heappop(h)
    u = temp%N
    r = temp//N
    for v in E[u]:
        if rnk[v] > r+1:
            continue
        rnk[v] = r+1
        par[v] = u
        heapq.heappush(h, (r+1)*N+v)

for p in par:
    print(p+1)

### FIXED CODE ###

N,M = map(int, input().split())
edge = [[] for _ in range(N)]
deg = [0]*N
parent = [[] for _ in range(N)]
for _ in range(N-1+M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1
    parent[y-1].append(x-1)
    
from collections import deque
res = list(v for v in range(N) if deg[v] == 0)
q = deque(res)
while q:
    v = q.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            res.append(t)
    
res.reverse()
f = [0]*N
for i in range(N):
    f[res[i]] = i
    
ans = [0]*N
for i in range(N):
    if parent[i]:
        temp = parent[i][0]
        for p in parent[i]:
            if f[temp] > f[p]:
                temp = p
        ans[i] = temp+1
        
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

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

    A.sort()

    i = 1
    j = N - 1
    while j > 0:
        if sum(A[:j]) * 2 >= A[j]:
            i += 1
        else:
            break
        j -= 1
    print(str(i))

main()

### FIXED CODE ###

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

    A.sort()
    i = 1
    j = N - 1
    x = sum(A)
    while j > 0:
        if (x - A[j]) * 2 >= A[j]:
            i += 1
        else:
            break
        x -= A[j]
        j -= 1
    print(str(i))

main()
### BUGGY CODE ###

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

while min(a) < n and k > 0:
  mark = [0] * (n + 1)
  for i in range(n):
    mark[max([0, i - a[i]])] += 1
    mark[min([n, i + a[i] + 1])] -= 1
  a = [mark[0]]
  for i in range(1, n):
    a.append(a[-1] + mark[i])
  k -= 1

print(' '.join(map(str, a)))

### FIXED CODE ###

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

while min(a) < n and k > 0:
  mark = [0] * (n + 1)
  for i in range(n):
    mark[max([0, i - a[i]])] += 1
    mark[min([n, i + a[i] + 1])] -= 1
  a = [mark[0]]
  for i in range(1, n):
    a.append(a[-1] + mark[i])
  k -= 1

print(' '.join(map(str, a)))
### BUGGY CODE ###

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

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
while(i < len(A)):
    j = i+1
    poplist = []
    while(j < len(A)):
        if A[j]%A[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if A[i]  == A[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるA[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        A.pop(k)
    # A[i]で割り切れるものは探しきって、次のA[i+1]は割り切れないもの。
    # 次はA[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    A.remove(i)

# print(A)
print(len(A))
# print(dellist)

### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

import sys
input = sys.stdin.readline

N = int(input())
S = input().rstrip('\r\n')
ans = 0
for i in range(1000):
    target = str(i).zfill(3)
    indices = [-1] * 3
    for m, c in enumerate(target):
        if m == 0:
            idx = S.find(c)
            if idx == -1:
                break
            indices[0] = idx
            continue
        for n in range(indices[m-1]+1, N):
            if c == S[n]:
                # print(target)
                indices[m] = n
                break
        if indices[0] > -1 and indices[1] > -1 and indices[2] > -1:
            ans += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input().rstrip('\r\n')
ans = 0
for i in range(1000):
    target = str(i).zfill(3)
    indices = [-1] * 3
    for m, c in enumerate(target):
        if m == 0:
            idx = S.find(c)
            if idx == -1:
                break
            indices[0] = idx
            continue
        for n in range(indices[m-1]+1, N):
            if c == S[n]:
                # print(target)
                indices[m] = n
                break
        if indices[0] > -1 and indices[1] > -1 and indices[2] > -1:
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]
ans = []
for i in range(n):
    if l[i] in ans:
        ans.remove(l[i])
    else:
        ans.append(l[i])
print(len(ans))

### FIXED CODE ###

n = int(input())
l = {}
ans = 0
for _ in range(n):
    a = int(input())
    if a in l:
        l[a] += 1
    else:
        l[a] = 1
for v in l.values():
    if v % 2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N=int(input())
ans=0
A=[0]*(N+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        A[j]+=j
print(sum(A))

### FIXED CODE ###

N=int(input())
ans=0
A=[0]*(N+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        A[j]+=j
print(sum(A))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

K = int(input())

if K % 2 == 0:
    print(-1)
    exit()

tmp = 7
i = 1

while True:
    if tmp % K == 0:
        print(i)
        exit()
    tmp = tmp * 10 + 7
    i += 1   

### FIXED CODE ###

K = int(input())

seen = set()

extra = 7 % K
i = 1

while extra not in seen:

    if extra == 0:
        print(i)
        exit()
    
    seen.add(extra)
    extra = (extra * 10 + 7) % K
    i += 1

print(-1)
### BUGGY CODE ###


from collections import defaultdict

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    mod = 10 ** 6 + 3
    num = int(input())
    for _ in range(num):
        x, d, n = map(int, input().split())
        if x == 0:
            print(0)
            continue
        ans = 1
        kari = x
        for i in range(n):
            ans *= kari
            kari += d
            ans %= mod
        print(ans % mod)



if __name__ == '__main__':
    main()
    # mod = 10 ** 9 + 7
    # print((71 * 312500008) % mod)

### FIXED CODE ###


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]
    mod = 10 ** 6 + 3

    origin = [0 for i in range(mod + 1)]
    origin[1] = 1
    for i in range(2, mod + 1):
        origin[i] = origin[i - 1] * i
        origin[i] %= mod

    for i in range(num):
        x, d, n = data[i]
        if d == 0:
            ans = pow(x, n, mod)
        else:
            t = x * pow(d, mod - 2, mod)
            t %= mod
            if t == 0 or t + n - 1 >= mod:
                ans = 0
            else:
                ans = origin[t + n - 1] * pow(origin[t - 1], mod - 2, mod)
                ans %= mod
                ans *= pow(d, n, mod)
                ans %= mod
        print(ans)

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import sqrt
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    A = set(A)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)

    def trial_division(n):
        divs = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divs.add(i)
                if i != n//i:
                    divs.add(n//i)
        divs.discard(n)
        return divs

    ans = 0
    for a in A:
        if a in bl:
            continue
        divs = trial_division(a)
        if not A & divs:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


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

N=int(input())
A=[input() for i in range(N)]
NA=[A.count(A[i]) for i in range(N)]
NIN=[i for i, v in enumerate(NA) if v == max(NA)]
NM=[A[NIN[i]] for i in range (len(NIN))]
NM=sorted(list(set(NM)))
for i in range (len(NM)):
    print(NM[i])

### FIXED CODE ###

N = int(input())
L = [input() for i in range(N)]
L = sorted(L)
D = {}

for i in L:
    if i in D:
        V = D.get(i) + 1
    else:
        V = 1
    D[i] = V

D = sorted(D.items(),key=lambda x:x[1],reverse=True)

Ans = []

Ans.append(D[0][0])

for i in range(len(D)-1):
    if D[i][1] == D[i+1][1]:
        Ans.append(D[i+1][0])
    else:
        break

Ans = sorted(Ans)

for i in Ans:
    print(i)
### BUGGY CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N // 2

for i in range(2, N + 1):
	j = 1
	
	while True:
		if i * j <= N:
			#print(i * j)
			
			ans += i * j
			j += 1
		else:
			break

print(ans)

### FIXED CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)