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

from collections import deque

def bfs(G, start):
    label[start] = start
    queue = deque()
    visited = [False] * (len(G))
    queue.append(start)
    while queue:
        target = queue.popleft()
        label[target] = start
        for j in G[target]:
            if visited[j] == False:
                visited[j] = True
                queue.append(j)
    visited = [k for k, x in enumerate(visited) if x ]
    return set(visited)

N, M, K = map(int, input().split())
F_G = [[] for _ in range(N)]
B_G = [[] for _ in range(N)]
label = [-1] * N
# 無向グラフの作成
for _ in range(M):
    a, b = map(int, input().split())
    F_G[a-1].append(b-1)
    F_G[b-1].append(a-1)
for _ in range(K):
    c, d = map(int, input().split())
    B_G[c-1].append(d-1)
    B_G[d-1].append(c-1)

sub = list(range(N))
# bfsでラベル付けすることで連結成分を作成
for i in sub:
    if label[i] == -1:
        bfs(F_G, i)
for i in sub:
    linked_node = [j for j, x in enumerate(label) if x == label[i]]
    linked_num = len(linked_node)
    next_to_num = len(F_G[i])
    block_num = len([k for k in linked_node if k in B_G[i]])
    if i != N-1:
        print(linked_num - next_to_num - block_num - 1, end=" ")
    else:
        print(linked_num - next_to_num - block_num - 1)

### FIXED CODE ###

N,M,K = map(int,input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(K)]

"""
Union-Find木実装のキモ(計算量削減)
1. Unionの工夫
   マージテク：大きい方を動かさずに小さい方をくっつける
2. Findの工夫
   経路圧縮 : 集合の要素を根に直接つなぎ変える.木をフラットにする.
"""

# Union-Findを用いて連結成分を考える(Union-Find木の実装)
class UnionFind:
    # まずは最初の状態を作る
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0

    # そのノードの根を返す過程で,集合の要素を根に直接つなぎかえる
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    # aとbの根が同じ,つまり同じ連結成分内かどうかを返す
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    # 連結成分同士を効率的に(rankが大きい方を動かさずにrankが小さい方をくっつける)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

blocks = [[] for _ in range(N)]
for c, d in CD:
    c, d = c-1, d-1
    blocks[c].append(d)
    blocks[d].append(c)

# friendsは友達の数を保持する
friends = [0] * N
uf = UnionFind(N)
for a,b in AB:
    a, b = a-1, b-1
    friends[a] += 1
    friends[b] += 1
    # aとbが同連結成分内であれば何もする必要がない
    if uf.is_same(a, b): continue
    # 異なれば結合
    uf.unite(a, b)

for i in range(N):
    uf.root(i)

from collections import Counter
ctr = Counter()
for i in range(N):
    r = uf.root(i)
    ctr[r] += 1

ans = []
for i in range(N):
    tmp = ctr[uf.root(i)] - friends[i] -1
    for b in blocks[i]:
        if uf.is_same(i, b):
            tmp -= 1
    ans.append(tmp)
print(*ans)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(m)]
heapq.heapify(a)

for i in range(m):
    b, c = query[i][0], query[i][1]
    for j in range(b):
        t = heapq.heappop(a)
        if t < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, t)

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1], reverse=True)

ans = 0
j = 0
for b, c in BC:
    for i in range(b):
        if j < n:
            ans += max(c, A[j])
            j += 1
        else:
            break

if j < n:
    for i in range(n - j):
        ans += A[n - 1 - i]

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

s = input()
n = len(s)
m = 2019

r = [0 for _ in range(m+1)]
r[0] = 1
for i in range(n):
    z = int(s[i:])%m
    r[z] += 1
a = 0
for i in range(m+1):
    a += r[i]*(r[i]-1)//2

print(a)


### FIXED CODE ###

s = input()
n = len(s)
m = 2019

a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
j = 1
for i in range(0,n):
    j = j * 10 % m
    ss = int(s[n-i-1])*j + z
    z = ss%m



    a += r[z]
    r[z] += 1

print(a)
### BUGGY CODE ###

import itertools
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab_results = []
for i in a:
    for j in b:
        ab_results.append(i + j)
ab_results.sort(reverse=True)

ab_results = ab_results[:k]
results = []
for i in c:
    for j in ab_results:
        results.append(i + j)
results.sort(reverse=True)
list(map(print, results[:k]))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

class item(object):
    def __init__(self,name,Value,weight):
        self.name=name
        self.value=Value
        self.weight=weight
    def getweight(self):
        return self.weight
    def getname(self):
        return self.name
    def getvalue(self):
        return self.value
    def __str__(self):
        res="<"+str(self.name)+","+str(self.value)+","+str(self.weight)+">"
        return res
"""def sumV(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getvalue
    return result
def sumW(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getweight
    return result"""
def maxVal(toConsider,avail,result):
    if toConsider==[] or avail==0:
        result+=0
    elif toConsider[0].getweight()>avail:
        result+=maxVal(toConsider[1:],avail,result)
    else:
        withval=toConsider[0].getvalue()+maxVal(toConsider[1:],avail-toConsider[0].getweight(),result)
        #とるかとらないかを選ぶ
        withoutval=maxVal(toConsider[1:],avail,result)
        if withval>withoutval:
            result+=withval
        else:
            result+=withoutval
    return result
N,W=map(int,input().split())
result=0
items=[]
for i in range(N):
    w,v=map(int,input().split())
    items.append(item(str(i),v,w))
"""for i in range(len(items)):
    print(items[i])"""
print(maxVal(items,W,result))





### FIXED CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))
### BUGGY CODE ###

import functools
import fractions

N = int(input())
T = list(map(int,input().split()))
T.sort()
ANSL = []
for i in range(len(T)):
    S = []
    for j in range(len(T)):
        S.append(T[j])
    S.pop(i)
    ANS = functools.reduce(fractions.gcd, S)
    ANSL.append(ANS)
print(max(ANSL))

### FIXED CODE ###

import copy 

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

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
m=a[0]
for i in range(n):
  m=m//eucrid(m,a[i])*a[i]
b=0
for i in a:
  b+=m*pow(i,mod-2,mod)%mod
print(b%mod)

### FIXED CODE ###

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

def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
m=a[0]
for i in range(n):
  m=m//eucrid(m,a[i])*a[i]
b=0
m=m%mod
for i in a:
  b+=m*pow(i,mod-2,mod)%mod
print(b%mod)
### BUGGY CODE ###

def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = map(int, my_input().split())
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = map(int, my_input().split())
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp[h][w][x] := h行w列にいて、h行からx個アイテムを拾っている時の価値の総和の最大値
    dp = [[[0] * 4 for j in range(W + 1)] for i in range(H + 1)]
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            for k in range(1, 4):
                dp[h][w][k] = max(
                    dp[h][w][k],
                    dp[h - 1][w][-1],
                    dp[h - 1][w][-1] + V[h - 1][w - 1],
                    dp[h][w - 1][k],
                    dp[h][w - 1][k - 1] + V[h - 1][w - 1])

    print(max(dp[-1][-1]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = map(int, my_input().split())
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = map(int, my_input().split())
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp1 ~ 4[h][w][x] := h行w列にいて、h行からn個アイテムを拾っている時の価値の総和の最大値
    dp0 = [[0] * (W + 1) for _ in range(H + 1)]
    dp1 = [[0] * (W + 1) for _ in range(H + 1)]
    dp2 = [[0] * (W + 1) for _ in range(H + 1)]
    dp3 = [[0] * (W + 1) for _ in range(H + 1)]

    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dp1[h][w] = max(
                dp1[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp1[h][w - 1],
                dp0[h][w - 1] + V[h - 1][w - 1]
            )

            dp2[h][w] = max(
                dp2[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp2[h][w - 1],
                dp1[h][w - 1] + V[h - 1][w - 1]
            )

            dp3[h][w] = max(
                dp3[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp3[h][w - 1],
                dp2[h][w - 1] + V[h - 1][w - 1]
            )

    print(dp3[-1][-1])


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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[]
ANS=N*(N-1)//2
for i in range(M-1,-1,-1):
  ans.append(ANS-sum([x*(x-1)//2 for x in uf.all_group_numbers()]))
  uf.union(AB[i][0]-1,AB[i][1]-1)
for i in range(len(ans)-1,-1,-1):
  print(ans[i])

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False,0,0

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    nx=self.size(x)
    ny=self.size(y)
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    return True,nx,ny

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  flg,na,nb=uf.union(a-1,b-1)
  if flg:
    ans[i]=ans[i+1]-na*nb
  else:
    ans[i]=ans[i+1]
  i-=1
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

from functools import reduce
INF = int(1e18)


def main():
    input()
    *A, = map(int, input().split())
    ans = reduce(lambda Ai, x: Ai * x, A)
    print(-1 if INF < ans else ans)
    return


main()


### FIXED CODE ###

INF = int(1e18)


def main():
    N, *A, = map(int, open(0).read().split())
    ans = 1
    if 0 in A:
        print(0)
        return
    for a in A:
        ans *= a
        if INF < ans:
            print(-1)
            break
    else:
        print(ans)
    return


main()
### BUGGY CODE ###

def main():
    n,a,b=map(int,input().split())
    x=n%(a+b)
    y=n//(a+b)
    if x in list(i for i in range(1,a+1)):
        print(a*y+x)
    elif x==0:
        print(a*y)
    else:
        print(a*(y+1))
main()

### FIXED CODE ###

n,a,b=map(int,input().split())
x=int(n/(a+b))
y=n%(a+b)
if a==0:
    print(0)
elif y==0:
    print(a*x)
elif 0<y<a+1:
    print(a*x+y)
else:
    print(a*(x+1))
### BUGGY CODE ###

from sys import stdin


def main():
    K, S = [int(x) for x in stdin.readline().rstrip().split()]
    result = 0
    for X in range(S + 1):
        for Y in range(S + 1):
            Z = S - (X + Y)
            if Z < 0:
                break
            if X <= K and Y <= K and Z <= K:
                result += 1
    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():
    K, S = [int(x) for x in stdin.readline().rstrip().split()]
    result = 0
    for X in range(S + 1):
        if K < X:
            break
        for Y in range(S + 1):
            if K < Y:
                break
            Z = S - (X + Y)
            if Z < 0:
                break
            if X <= K and Y <= K and Z <= K:
                result += 1
    print(result)


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

n = int(input())
an = [int(x) for x in input().split()]
print(min([abs(sum(an[:x])-sum(an[x:])) for x in range(1,n)]))


### FIXED CODE ###

n = int(input())
an = [int(x) for x in input().split()]
an_sum = sum(an)
x_sum = 0
ans = 1e10
for x in range(0,n-1):
    x_sum += an[x]
    ans = min(ans, abs(an_sum-2*x_sum))
print(ans)
### BUGGY CODE ###


n = int(input())
ans = 0

for i in range(n):
    ans += i

print(ans)


### FIXED CODE ###

n = int(input())
ans = ((n-1)*n)//2

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

S = list(input())

for i,c in enumerate(S):
    if len(S[i:]) == 2:
        subset = S[i:i+2]
        if subset[0] == subset[1]:
            print("%d %d" % (i+1, i+2))
            break   
        continue    
        
    elif len(S[i:]) > 2:
        subset = S[i:i+3]
        if subset[0] == subset[2] or subset[1] == subset[2]:
            print("%d %d" % (i+1, i+3))    
            break
        continue   

    else:
        print("-1 -1")

### FIXED CODE ###

import sys
S = list(input())
if len(S) == 2 and S[0] == S[1]:
    print("%d %d" % (1, 2))
    sys.exit()

for i in range(len(S) - 2):
    subset = S[i:i+3]
    if subset[0] == subset[2] or subset[1] == subset[2]:
        print("%d %d" % (i+1, i+3))    
        sys.exit()

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

import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L = sorted(L)
    count = 0
    for i in reversed(range(2,N)):
        for j in reversed(range(1,i)):
            cind = bisect.bisect_right(L,L[i]-L[j])
            
            for k in range(cind,j):
                if L[i]<L[j]+L[k]:
                    count += 1
    print(count)
main()

### FIXED CODE ###

import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    
    count = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            c = bisect.bisect_left(L,L[i]+L[j])
            
            count += max(0,c-1 - j)
    
    print(count)
main()
### BUGGY CODE ###

N=raw_input()
n=int(N)

AN=raw_input().split()
an=[int(i) for i in AN]

on = [str(an.index(i+1) + 1) for i in range(len(an))]
print " ".join(on)

### FIXED CODE ###

N=raw_input()
n=int(N)

AN=raw_input().split()
an=[int(i) for i in AN]

on = [(i+1,an[i]) for i in range(len(an))]

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

on = [str(i[0]) for i in on]



print " ".join(on)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
from collections import deque
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
n, k = M()
A = deque(LI())
ans = deque()
for i in range(n-1, k-1, -1):
    if A[i] > A[i-k]:
        ans.appendleft('Yes')
    else:
        ans.appendleft('No')
for s in ans:
    print(s)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
from collections import deque
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
n, k = M()
A = deque(LI())
ans = deque()
for i in range(k, n):
    if A[i] > A[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

danmen = input()
depth = []
tmp_dpt = 0

for line in danmen:
    depth.append(tmp_dpt)

    if line == "\\":
        tmp_dpt -= 1
    elif line == "/":
        tmp_dpt += 1

depth.append(tmp_dpt)

# print(depth)

i = 0
L = []

while i < len(danmen):
    if danmen[i] == "\\":
        if depth[i] in depth[i + 1:]:
            stack = 0
            area = 0

            for line in danmen[i:]:
                if line == "\\":
                    area += 1 + 2 * stack
                    stack += 1
                elif line == "/":
                    stack -= 1
                    area += 1 + 2 * stack
                else:
                    area += 2 * stack

                if stack == 0:
                    break

            if area != 0:
                L.append(area // 2)
                i += depth[i + 1:].index(depth[i])
        
    i += 1

print(sum(L))
print(len(L), *L)

### FIXED CODE ###


danmen = input()

down = []
edge = []
pool = []

for (i, line) in enumerate(danmen):
    if line == "\\":
        down.append(i)
    elif down and line == "/":
        left = down.pop()
        area = i - left

        while edge:
            if edge[-1] < left:
                break
            edge.pop()
            area += pool.pop()

        edge.append(left)
        pool.append(area)

print(sum(pool))
print(len(pool), *pool)
### BUGGY CODE ###

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

dp = [0]*(10**6)
count = [0]*(10**6)
for i in a:
  count[i-1] += 1
  m = 2
  while i*m <= 10**6:
    dp[i*m-1] = 1
    m += 1
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

### FIXED CODE ###

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

for i in a:
  count[i-1] += 1
 
b = list(set(a))
for i in b:
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)
### BUGGY CODE ###

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


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


p=1
h=[]
go=0


for i in range(1,k+1):
    
    
    
    

    h.append(p)
    p=a[p-1]
    
    if p in h:
        j=h.index(p)
        amari=(k-i-1)%(i-j)
        p=h[j+amari]
        go=1
        break

if go==1:
    p=a[p-1]

print(p)


### FIXED CODE ###

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i-1
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    
    


print(p)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = set(a)
count = 0
for i in b:
    x = a.count(i) 
    if x < i:
        count += x
    else:
        count += x - i
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
count = 0
x = 0
tmp_count = 0
for i in a:
    if i != x:
        if tmp_count < x:
            count += tmp_count
        else:
            count += tmp_count - x
        tmp_count = 1
        x = i
    else:
        tmp_count += 1
if tmp_count < x:
    count += tmp_count
else:
    count += tmp_count - x
print(count)
### BUGGY CODE ###

import sys, re
import math
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul	# 
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd	# 最大公約数
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# -*- coding: utf-8 -*-
n = INT()
list = []

addFlag = True

for x in range(n):
    text = input()
    addFlag = True
    for y in list:
        if text == y:
            addFlag = False
            break
    if addFlag:
        list.append(text)
        
print(len(list))

### FIXED CODE ###

import sys
import collections

n = int(sys.stdin.readline().strip())
data = []

for x in range(n):
    data.append(input())

print(len(collections.Counter(data)))