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

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

N = int(input())
X = input()

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

import itertools
N, M = map(int, input().split())
xyz = list()
for n in range(N):
    xyz.append([int(x) for x in input().split()])
ans = 0
for x in itertools.combinations(range(N), M):
    tmp = [0,0,0]
    for m in x:
        for y in range(3):
            tmp[y] += xyz[m][y]
    ans = max(ans, sum([abs(x) for x in tmp]))
print(ans)


### FIXED CODE ###

import itertools
N, M = map(int, input().split())
xyz = list()
for n in range(N):
    xyz.append([int(x) for x in input().split()])
ans = 0
for a,b,c in itertools.product([-1,1], repeat=3):
    tmp = []
    for x, y, z in xyz:
        tmp.append(a*x+b*y+c*z)
    tmp.sort(reverse=True)
    ans = max(ans, sum(tmp[:M]))
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
for k in range(1,N + 1):
    for i,j in zip(L,R):
        if i <= k and k <= j:
            continue
        else:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
L_max = max(L)
R_min = min(R)
for i in range(L_max,min(R_min,N) + 1):
    ans  += 1
print(ans)
### BUGGY CODE ###

N = int(input())

point = []
dist = []

for _ in range(N) :
    x, y = map(int, input().split())
    point.append((x, y))
    dist.append(abs(x) + abs(y))

distSort = sorted(dist)
maxDist = distSort[-1]
for d in distSort :
    if (maxDist - d) % 2 == 1 :  # 実現不可能
        print('-1')
        break
else :  # 実現可能
    print(maxDist) # 腕の数
    for _ in range(maxDist) :
        print('1 ', end='')
    print('')
    for x, y in point :
        for _ in range(abs(x)) :
            if x < 0 :
                print('L', end='')
            else :
                print('R', end='')
        for _ in range(abs(y)) :
            if y < 0 :
                print('D', end='')
            else :
                print('U', end='')
        for i in range((maxDist - (abs(x) + abs(y))) // 2) :
            print('LR', end='')
        print('')



### FIXED CODE ###

N=int(input())

point = []
parity = {}
for _ in range(N) :
    x, y = map(int, input().split())
    point.append((x, y))
    parity[(x + y) % 2] = 1

if len(set(parity)) == 2 :
    print('-1')
else :
    m = 38
    parity = 1 if (1 in parity) else 0
    print(m + 1 - parity)
    if parity == 1 :  # 距離が奇数
        print(*[1 << i for i in range(m)])
    else :
        print(1, *[1 << i for i in range(m)])

    def arm(x, y, m) :
        if abs(x) >= abs(y) :
            if x >= 0 :
                return ('R', x - (1<<m), y)
            else :
                return ('L', x + (1<<m), y)
        else :
            if y >= 0 :
                return ('U', x, y - (1<<m))
            else :
                return ('D', x, y + (1<<m))

    for x, y in point :
        ans = []
        for i in range(m-1, -1, -1) :
            mode, x, y = arm(x, y, i)
            ans.append(mode)
        if parity == 0 :  # 偶数の場合一つ足す
            if x == 1 :
                ans.append('R')
            elif x == -1 :
                ans.append('L')
            elif y == 1 :
                ans.append('U')
            elif y == -1 :
                ans.append('D')
        print(''.join(ans[::-1]))
### BUGGY CODE ###

from collections import deque
N, X, Y = list(map(int, input().split()))

# N = 2000
# X = 100
# Y = 1900

X -= 1
Y -= 1


# @profile
def main(N, X, Y):
    ans = [0]*N
    for sv in range(N):
        # dist[v] = dist from sv to v
        dist = [float("inf")]*N
        visited = deque()
        dist[sv] = 0
        visited.appendleft(sv)
        while visited:
            v = visited.pop()
            d = dist[v]
            if v+1 < N and dist[v+1] == float("inf"):
                dist[v+1] = d+1
                visited.appendleft(v+1)
            if v-1 >= 0 and dist[v-1] == float("inf"):
                dist[v-1] = d+1
                visited.appendleft(v-1)
            if v == X and dist[Y] == float("inf"):
                dist[Y] = d+1
                visited.appendleft(Y)
            if v == Y and dist[X] == float("inf"):
                dist[X] = d+1
                visited.appendleft(X)
        # print(dist)
        for d in dist:
            ans[d] += 1

    for a in ans[1:]:
        print(a//2)


main(N, X, Y)


### FIXED CODE ###


N, X, Y = list(map(int, input().split()))

# N = 2000
# X = 100
# Y = 1900


X -= 1
Y -= 1

# @profile


def main(N, X, Y):
    ans = [0]*N
    for i in range(N):
        for j in range(i+1, N):
            d = min(j-i, abs(X-i)+abs(Y-j)+1)
            ans[d] += 1

    for a in ans[1:]:
        print(a)


main(N, X, Y)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
g = [[] for i in range(n)]
sg = [set() for i in range(n)]
lsg = [0]*n
seen = [-1]*n
fin = set()
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    sg[a-1].add(b-1)
    sg[b-1].add(a-1)
for i in range(n):
    lsg[i] = len(g[i])
# print(sg)
def dfs(node,parent):
    cnt = lsg[parent] - len(sg[parent] - fin) +1
    # print(cnt)
    seen[node] = k-cnt
    fin.add(node)
    for v in g[node]:
        if seen[v] == -1:
            dfs(v,node)
fin.add(0)
seen[0] = k
for i in g[0]:
    dfs(i,0)
res = 1
for x in seen:
    res *= x
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# class Combination:
#     """
#     comb = Combination(1000000)
#     print(comb(5, 3))  # 10
#     """
#     def __init__(self, n_max, mod=10**9+7):
#         self.mod = mod
#         self.modinv = self.make_modinv_list(n_max)
#         self.fac, self.facinv = self.make_factorial_list(n_max)

#     def __call__(self, n, r):
#         return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

#     def make_factorial_list(self, n):
#         # 階乗のリストと階乗のmod逆元のリストを返す O(n)
#         # self.make_modinv_list()が先に実行されている必要がある
#         fac = [1]
#         facinv = [1]
#         for i in range(1, n+1):
#             fac.append(fac[i-1] * i % self.mod)
#             facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
#         return fac, facinv

#     def make_modinv_list(self, n):
#         # 0からnまでのmod逆元のリストを返す O(n)
#         modinv = [0] * (n+1)
#         modinv[1] = 1
#         for i in range(2, n+1):
#             modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
#         return modinv


n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,i):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = 0
    for v in g[cur]:
        if v == par:
            continue
        cnt += 1
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)
### BUGGY CODE ###

length = list(map(int,input().split()))	
string = input()
l_r = [list(map(int,input().split())) for i in range(length[1])]
answer = []

for i in range(length[1]):
  part_str = string[(l_r[i][0]-1):l_r[i][1]]
  for n in range(len(part_str)):
    answer.append(0)
    if part_str[n]=='A':
      if n != (len(part_str)-1):
        if part_str[n+1]=='C':
          answer[i] += 1
  print(answer[i])
          

### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
ans = ''
a = [0]
count = 0
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    ans += '1'
  else:
    ans += '0'
  if i == N - 2:
    ans += '0'
else:
  for i in range(N):
    if ans[i] == '1':
      count += 1
      a.append(count)
    else:
      a.append(count)
  else:
    for i in range(Q):
      l = lr[i][0]
      r = lr[i][1]
      print(a[r-1]-a[l-1])
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]


def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	mod = 10**9 + 7
	N = int(input())
	A = tuple(map(int, input().split()))

	ans = reduce(lcm, A) 
	
	B = (ans//i for i in A)
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

def solve(sh,sw,gh,gw):
    if s[sh][sw]=="#" or s[gh][gw]=="#":
        return -1

    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if hi+dh==gh and wi+dw==gw:
                    return r+1
                elif not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))

    return -1

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        for ghi in range(h):
            for gwi in range(w):
                if shi>=ghi and swi>=gwi:
                    continue
                r = solve(shi,swi,ghi,gwi)
                res = max(res, r)

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

maxr = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi]==".":
            maxr += 1

def solve(sh,sw):
    res = -1
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))
                    res = max(res, r+1)

    return res

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        r = solve(shi,swi)
        res = max(res, r)

print(res)
### BUGGY CODE ###

import numpy as np
from numba import jit

@jit
def solve(s):
    n = len(s)
    ans = 0
    now = 0
    mp = np.zeros(2019, np.int32)
    mp[0] += 1
    tmp = np.zeros(2019, np.int32)

    id = np.zeros(2019, np.int32)
    for i in range(2019):
        id[i] = i * 10 % 2019

    for c in s:
        now *= 10;
        now += ord(c) - ord("0")
        now %= 2019

        ans += mp[now]
        mp[now] += 1
        for i in range(2019):
            tmp[id[i]] = mp[i]
        for i in range(2019):
            mp[i] = tmp[i]

    print(ans)

s = input()
solve(s)


### FIXED CODE ###

s = input()
n = len(s)
ans = 0
now = 0
mp = [0 for i in range(2019)]
mp[0] += 1
tmp = [0 for i in range(2019)]

id = [0 for i in range(2019)]
for i in range(2019):
    id[i] = i * 10 % 2019

for c in s:
    now *= 10;
    now += ord(c) - ord("0")
    now %= 2019

    ans += mp[now]
    mp[now] += 1
    for i in range(2019):
        tmp[id[i]] = mp[i]
    for i in range(2019):
        mp[i] = tmp[i]

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

from collections import Counter

while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]
    all_H = []
    all_W = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            all_H.append(sum(H[i:j]))
    for i in range(M):
        for j in range(i + 1, M + 1):
            all_W.append(sum(W[i:j]))
    all_H = Counter(sorted(all_H))
    all_W = Counter(sorted(all_W))

    ans = 0
    for k, v in all_H.items():
        if k in all_H:
            ans += v * all_W[k]
    # print(all_H)
    # print(all_W)
    print(ans)



### FIXED CODE ###

from collections import Counter

while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]

    all_H = []
    for i in range(N):
        s = 0
        for j in range(i, N):
            s += H[j]
            all_H.append(s)

    all_W = []
    for i in range(M):
        s = 0
        for j in range(i, M):
            s += W[j]
            all_W.append(s)

    all_H = Counter(all_H)
    all_W = Counter(all_W)
    ans = 0
    for k, v in all_H.items():
        if k in all_H:
            ans += v * all_W[k]
    print(ans)
### BUGGY CODE ###

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

score = 1

for i in range(k):
    score *= a[i]

for j in range(k,n):
    score_before = score
    score =  score * a[j] // a[j-k]
    #print('score_befor',score_before)
    #print('score',score)
    if score_before < score:
        print('Yes')
    else:
        print('No')
    

### FIXED CODE ###

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

for i in range(k,n):
    if a[i-k] < a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from itertools import permutations
l, r = map(int,input().split())
a = []
for i in range(l,r+1):
    tmp = i%2019
    if tmp not in a:
        a.append(tmp)
perm = permutations(a,2)
min = 2019
for i in list(perm):
    tmp = i[0]*i[1]%2019
    if min > tmp:
        min = tmp
print(min)


### FIXED CODE ###

import sys
l, r = map(int, input().split())
if r-l>=2019:
    print("0")
elif r%2019==0 or l%2019==0:
    print("0")
else:
    min = 2019
    for i in range(l,r):
        for j in range(i+1,r+1):
            tmp = i*j%2019
            if min > tmp:
                min = tmp
            if min == 0:
                print("0")
                sys.exit()
    print(min)
### BUGGY CODE ###

import numpy as np

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

dis = 300000000

for i in range(N-K+1):
    y = list(x[i:i+K])
    if (y[0]*y[-1]<0):
        disy = y[-1]-y[0]+min(abs(y[-1]), abs(y[0]))
    else:
        disy = max(abs(y[0]), abs(y[-1]))
    dis = min(dis, disy)

print(dis)

### FIXED CODE ###

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

dis = 300000000

for i in range(N-K+1):
    disl = abs(x[i]) + abs(x[i+K-1]-x[i])
    disr = abs(x[i+K-1]) + abs(x[i+K-1]-x[i])

    dis = min(dis, disl, disr)
#    if (y[0]*y[-1]<0):
#        disy = y[-1]-y[0]+min(abs(y[-1]), abs(y[0]))
#    else:
#        disy = max(abs(y[0]), abs(y[-1]))
#    dis = min(dis, disy)

print(dis)
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w,k = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())
x1,y1,x2,y2 = x1-1,y1-1, x2-1,y2-1
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]

def make_array(dims, fill):
    if len(dims) == 1:
        return [fill]*dims[0]
    nxt = dims[1:]
    ret = [make_array(nxt,fill) for i in range(dims[0])]
    return ret

inf = float("inf")

DP = make_array((h,w,4), inf)

from collections import deque
que = deque()
for i in range(4):
    que.append((x1,y1,i,0))

dxdy = [(-1,0),(1,0),(0,1),(0,-1)]
while que:
    x,y,prev,cost = que.popleft()
    if DP[x][y][prev] <= cost:
        continue
    DP[x][y][prev] = cost
    for i in range(4):
        if i == prev:
            continue
        nprev = i^1
        ddx, ddy = dxdy[i]
        for j in range(1,k+1):
            nx, ny = x+j*ddx, y+j*ddy
            if not (0<=nx<h and 0<=ny<w and board[nx][ny]):
                break
            if DP[nx][ny][nprev] > cost+1:
                que.append((nx,ny,nprev,cost+1))

ans = min(DP[x2][y2])
if ans == inf:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            # コストが変わらない場合は無視か...
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure = sorted(closure, key=lambda x: x[0])

    D = []
    for _ in range(Q):
        D.append(int(input()))

    D.sort()

    d = defaultdict(lambda: 0)
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        for blocked in D[left:right]:
            d[blocked] = pos

        D = D[0:left] + D[right:]

    for blocked in D:
        d[blocked] = -1

    for key in sorted(d.keys()):
        print(d[key])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# ref: https://atcoder.jp/contests/abc128/submissions/5654623

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

    D = [int(input()) for _ in range(Q)]

    ans = [-1] * Q
    skip = [-1] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        while left < right:
            if skip[left] == -1:
                ans[left] = pos
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')
### BUGGY CODE ###

import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1]:
            prime[A[i]] = False
            for j in range(A[i] * 2, MAX, A[i]):
                prime[j] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1] and prime[A[i]]:
            prime[A[i]] = False
            for j in range(A[i] * 2, MAX, A[i]):
                prime[j] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()