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

N = int(input())

initial = (1,1,1)
queue = []
queue.append(initial)
pointer = 0
answers = [0] * (N + 1)
while pointer < len(queue):
    x, y, z = queue[pointer]
    # print(x, y, z)
    q = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
    if q < N + 1:
        answers[q] += 1
        if x >= y and x >= z:
            queue.append((x + 1, y, z))
        if y >= z:
            queue.append((x, y + 1, z))
        queue.append((x, y, z + 1))
    pointer += 1

        
for a in answers[1:N + 1]:
    print(a)

### FIXED CODE ###

N = int(input())

initial = (1,1,1)
queue = []
queue.append(initial)
pointer = 0
answers = [0] * (N + 1)
memo = {}
while pointer < len(queue):
    x, y, z = queue[pointer]
    # print(x, y, z)
    q = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
    if q < N + 1:
        add = 1
        if x == y and y == z:
            add = 1
        elif x == y or y == z or z == x:
            add = 3
        else:
            add =6
        answers[q] += add

        if x+1>=y and y >=z and (x+1,y,z) not in memo:
            memo[(x+1,y,z)] = 0
            queue.append((x + 1, y, z))
        if x >= y +1 and y + 1 >= z and (x, y+1, z) not in memo:
            memo[(x,y+1,z)] = 0
            queue.append((x, y + 1, z))
        if x >= y and y >= z+1 and (x, y, z+1) not in memo:
            memo[(x,y,z+1)] = 0
            queue.append((x, y, z + 1))
    pointer += 1

        
for a in answers[1:N + 1]:
    print(a)
### BUGGY CODE ###

N, K = map(int,input().split())
max=0
t=list(input().split())
s=[int(n) for n in t]
for i in range(N-K+1):
    x=sum(s[i:i+K])
    if max<x :
        max=x
print((max+K)/2)


### FIXED CODE ###

N, K = map(int,input().split())
t=list(input().split())
s=[int(n) for n in t]
max=x=sum(s[:K])
for i in range(N-K):
    x+=(s[K+i]-s[i])
    if max<x :
        max=x
print((max+K)/2)
### BUGGY CODE ###

import sys
from sys import stdin
def input(): return sys.stdin.readline().strip()

N = int(input())
pn = list(map(float,input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j] * pn[i]
        dp[i+1][j] += dp[i][j] * (1 -pn[i])
n2 = N // 2 + 1
ans = 0
for k in range(n2 , N+1):
    ans  += dp[N][k]
print(ans)

### FIXED CODE ###

import sys
from sys import stdin
def input(): return sys.stdin.readline().strip()
import numpy as np

N = int(input())
pn = list(map(float,input().split()))
dp = np.array([0.0] * (N+1))
dp[0] = 1.0
for i in range(N):
    tmp = dp * (1-pn[i])
    tmp[1:] += dp[:-1] * pn[i]
    dp = tmp

print(sum(dp[N // 2 +1:]))
### BUGGY CODE ###


iN,iM = [int(_) for _ in input().split()]

if iM % iN == 0:
    print(iM // iN)
else:
    aRet = []
    for i in range(1,iM//iN + 1):
        if iM % i == 0:
            aRet.append(i)
    print(aRet[-1])


### FIXED CODE ###

iN,iM = [int(_) for _ in input().split()]

if iM % iN == 0:
    print(iM // iN)
else:
    aRet = []
    for i in range(1,iM//iN + 1):
        if iM % i == 0:
            aRet.append(i)
    print(aRet[-1])
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())

p = np.array(input().split(),np.int)

ans = 0
qs = (p + 1)/2
for i in range(n-k+1):
    ps = qs[i:(i+k)]
    ans = max(ans,sum(ps))


print(ans)


### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())

p = np.array(input().split(),np.int)


fs = p[:k]
f = sum(fs)
m = n - k + 1
qs = np.zeros(m)
qs[0] = f
if n == k:
    ans = (f + k)/2
    print(ans)
else:
    for i in range(k,n):
        a = qs[i-k] - p[i-k] + p[i]
        qs[i-k+1] = a
    ans = (max(qs)+k) / 2
    print(ans)
### BUGGY CODE ###

n = int(input())
word = [input() for i in range(n)]
test = list([x,word.count(x)] for x in set(word))
max_num = int(max(test, key=lambda x: x[1])[1])

print('\n'.join(sorted([num[0] for num in test if int(num[1]) == max_num])))


### FIXED CODE ###

from collections import Counter
n = int(input())
word = Counter([input() for i in range(n)]).most_common()
print('\n'.join(sorted([num[0] for num in word if int(num[1]) == word[0][1]])))
### BUGGY CODE ###

n,p=map(int,input().split())
s=input()
print( sum(int(s[i:j+1])%p==0 for i in range(n) for j in range(i,n)) )

### FIXED CODE ###

#e
n,p=map(int,input().split())
s=input()
ans=0
if p == 2:
    for i in range(n):
        if s[i] in ["0","2","4","6","8"]:
            ans+=i+1
elif p == 5:
    for i in range(n):
        if s[i] in ["0","5"]:
            ans+=i+1
else:
    mod=[1] + [0]*(p-1)
    a=0
    for i in range(n):
        si = int( s[n-1-i] )
        a = si*pow(10,i,p) + a 
        mod[ a%p ]+=1
    ans =  sum(m*(m-1)//2 for m in mod)
print(ans)
### BUGGY CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(n)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])
				# w_v_list[i][1] = 0
			else:
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
	# for i in dp:print(*i)
	print(dp[n-1][w])




if __name__ == "__main__":
	solve()

### FIXED CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(n)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])
				# w_v_list[i][1] = 0
			else:
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
	# for i in dp:print(*i)
	print(dp[n-1][w])




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

N, K, Q = map(int, input().split())
who_answered = [None]*Q
participants = [K]*N

for i in range(Q):
    who_answered[i] = int(input()) - 1
    participants[who_answered[i]] += 1
    for j in range(N):
        participants[j] -= 1

for i in range(N):
    if participants[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
who_answered = [None]*Q
participants = [K-Q]*N

for i in range(Q):
    who_answered[i] = int(input()) - 1
    participants[who_answered[i]] += 1

for i in range(N):
    if participants[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
s = input()

ans = float('inf')

for i in range(n):
  counter = 0
  for j in range(n):
    if j < i and s[j] == 'W':
      counter += 1
    if j > i and s[j] == 'E':
      counter += 1
  ans = min(ans,counter)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = float('inf')
w_left = [0]*n
e_right = [0]*n

for i in range(1,n):
  if s[i-1] == 'W':
    w_left[i] = w_left[i-1]+1
  else :
    w_left[i] = w_left[i-1]
      
for i in range(1,n):
  if s[n-i] == 'E':
    e_right[n-i-1] = e_right[n-i]+1
  else :
    e_right[n-i-1] = e_right[n-i]

for i in range(n):
    if ans > w_left[i]+e_right[i]:
        ans = w_left[i]+e_right[i]
print(ans)
### BUGGY CODE ###

def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n=int(input())
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print(ans%mod)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a=1
B=[1,1]
mod=10**9+7
for i in range(2,n):
  a=a*i%mod
  B.append(pow(i,mod-2,mod))
d=[0]*(n-1)
for i in range(n-1):
  d[i]=x[i+1]-x[i]
D=[d[-1]]
for i in range(n-2):
  D.append(D[-1]+d[-2-i])
D=D[::-1]
ans=0
for i in range(n-1):
  ans=(ans+D[i]*a*B[i+1])%mod
print(ans)
### BUGGY CODE ###

import numpy as np
def solve(n, t, a, b):
    prefix = np.zeros((n+1, t+1), dtype=int)
    suffix = np.zeros((n+1, t+1), dtype=int)
    for i in range(n):
        prefix[i+1] = prefix[i]
        for j in range(t):
            nj = j+a[i]
            if nj <= t:
                prefix[i+1, nj] = max(prefix[i+1, nj], prefix[i, j] + b[i])
    for i in range(n-1, -1, -1):
        suffix[i] = suffix[i+1]
        for j in range(t):
            nj = j+a[i]
            if nj <= t:
                suffix[i, nj] = max(suffix[i, nj], suffix[i+1, j] + b[i])
    for i in range(n+1):
        for j in range(t):
            prefix[i, j+1] = max(prefix[i, j+1], prefix[i, j])
            suffix[i, j+1] = max(suffix[i, j+1], suffix[i, j])
    best = 0
    for i in range(n):
        for j in range(t):
            cur = prefix[i,j] + b[i] + suffix[i+1,t-1-j]
            best = max(best, cur)
    return best

n, t = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(n, t, a, b))



### FIXED CODE ###

import numpy as np
def solve(n, t, a, b):
    dp = np.zeros(t, dtype=int)
    candidates = []
    for w, v in sorted(zip(a, b)):
        candidates.append(dp[-1] + v)
        if w > t:
            continue
        dp[w:] = np.maximum(dp[:-w] + v, dp[w:])
    return np.max(candidates)

n, t = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(n, t, a, b))
### BUGGY CODE ###

import math

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

for i in range(N):
  for j in range(1,N-i):
    #print(i,j,A[i],A[j])
    if A[i]+A[i+j]==j:
      c+=1
print(c)

### FIXED CODE ###

n=int(input())
A=list(map(int, input().split()))
d={}
c=0

for i,a in enumerate(A):
  if i+a not in d:
    d[i+a]=1
  else:
    d[i+a]+=1
  if i-a in d:
    c+=d[i-a]

print(c)
### BUGGY CODE ###


import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    treasures.sort(lambda a, b: cmp(b.value, a.value))
    tvw = (0, 0)
    for ts in t_combinations(treasures):
        w = t_sum_weight(ts)
        if w <= w_limit:
            v = t_sum_value(ts)
            if tvw[0] < v:
                 tvw = (v, w)
            elif tvw[0] == v:
                 if w < tvw[1]:
                     tvw = (v, w)
    return tvw


def t_combinations(t):
    l = len(t)
    for x in range(l, 0, -1):
        for y in itertools.combinations(t, x):
            yield y


def t_sum_weight(ts):
    return sum(map(lambda x: x.weight, ts))


def t_sum_value(ts):
    return sum(map(lambda x: x.value, ts))


def rightest(tss):
    return reduce(lambda a, b: take_right(a, b), tss)


def take_right(a, b):
    if t_sum_weight(a) <= t_sum_weight(b):
        return a
    else:
        return b


case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

### FIXED CODE ###


import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    dp = []
    dp.append(0)
    for n in range(w_limit):
        dp.append(-1)
    for i in treasures:
        for j in range(w_limit - i.weight, -1, -1):
            if dp[j] >= 0:
                dp[j + i.weight] = max(dp[j + i.weight], dp[j] + i.value)
    p = 0
    q = 0
    for i in range(w_limit + 1):
        if dp[i] > p:
            p = dp[i]
            q = i
    return (p, q)






case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import numpy as np
input = sys.stdin.readline


def main():
    n = int(input())
    l = np.array(list(map(int, input().split())))
    l = np.sort(l)

    result = 0
    # print(l)
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            target = l[j + 1:]
            count = sum(1 for x in target if x < (l[i] + l[j]))
            # count = np.count_nonzero(target < (l[i] + l[j]))
            # print(l[i], l[j], target, count)
            result += count

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            result += bisect.bisect_left(l, l[i] + l[j]) - (j + 1)

    print(result)


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

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

a=input().split()

l=len(a)

for i in range(0,l):
    a[i]=int(a[i])

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,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)



### FIXED CODE ###

n,m = map(int,input().split())
dp = [0]+[10**8+10]*(2**n-1)
for i in range(m):
  a,b = map(int,input().split())
  s = sum([2**(x-1) for x in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|s] = min(dp[j|s],dp[j]+a)
if dp[-1] <= 10**8:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in set(a):
    dic.setdefault(i, a.count(i))
ans = 0
for i in dic.values():
    if i > 1:
        ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in a:
    if i not in dic.keys():
        dic[i] = 1
    else:
        dic[i] += 1
for i in dic.values():
    ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))
### BUGGY CODE ###

cookie = list(map(int, input().split()))
sc = sum(cookie)
cnt = -1
if cookie[0] == cookie[1] and cookie[1] == cookie[2]:
    if cookie[0] % 2 == 0:
        print(cnt)
        exit()
    else:
        print(0)
memo = [0]*3
while sum(cookie) == sc:
    memo[0] = (cookie[1] + cookie[2]) // 2
    memo[1] = (cookie[0] + cookie[2]) // 2
    memo[2] = (cookie[1] + cookie[0]) // 2
    for i in range(3):
        cookie[i] = memo[i]
    cnt += 1

print(cnt)

### FIXED CODE ###

cookie = list(map(int, input().split()))
sc = sum(cookie)
cnt = 0
if cookie[0] == cookie[1] and cookie[1] == cookie[2] and cookie[0]%2 == 0:
    print(-1)
    exit()
memo = [0]*3
while cookie[0]%2 == 0 and cookie[1]%2 == 0 and cookie[2]%2 == 0:
    memo[0] = (cookie[1] + cookie[2]) // 2
    memo[1] = (cookie[0] + cookie[2]) // 2
    memo[2] = (cookie[1] + cookie[0]) // 2
    for i in range(3):
        cookie[i] = memo[i]
    cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()

n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

p = [0] * n
for _ in range(q):
    pp, x = [int(i) for i in input().split()]
    p[pp - 1] += x


def dfs(i=0, r=-1, po=0):
    p[i] += po
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i,p[i])
dfs()

print(" ".join(map(str,p)))

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

import sys, os, math

def get_cd(n):
    cd = []
    for i in range(1, int(n/2)+1):
        if n % i == 0:
            cd.append(i)
        else:
            continue
    cd.append(n)
    return cd

def get_gcd(a, b, c, cd_d):
    if 1 in [a, b, c]:
        return 1
    else:
        min_v = min([a,b,c])
        cds_min = cd_d[min_v]
        gcd = 1
        for cd in reversed(cds_min):
            if cd in cd_d[a]:
                if cd in cd_d[b]:
                    if cd in cd_d[c]:
                        return cd
                    else: continue
                else: continue
            else:continue

if __name__ == '__main__':
    k = int(input())
    cc_d = {}
    for i in range(1, k+1):
        cc_d[i] = get_cd(i)

    computed_d = {}
    s = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                sort_str = "".join([ str(i) for i in sorted([a,b,c])])
                if  sort_str in computed_d.keys():
                    gcd = computed_d[sort_str]
                else:
                    gcd = get_gcd(a, b, c, cc_d)
                    computed_d[sort_str] = gcd
                s += gcd
    print(s)

### FIXED CODE ###

import sys, os, math

def get_cd(n):
    cd = []
    for i in range(1, int(n/2)+1):
        if n % i == 0:
            cd.append(i)
        else:
            continue
    cd.append(n)
    return cd

def get_gcd(a, b, c, cd_d):
    if 1 in [a, b, c]:
        return 1
    else:
        cd = sorted(list(set(cd_d[a]) & set(cd_d[b]) & set(cd_d[c])))
        return cd[-1]

if __name__ == '__main__':
    k = int(input())
    cc_d = {}
    for i in range(1, k+1):
        cc_d[i] = get_cd(i)

    computed_d = {}
    s = 0
    for a in range(1, k+1):
        for b in range(a, k+1):
            for c in range(b, k+1):
                if a == b == c:
                    s += a
                else:
                    gcd = get_gcd(a, b, c, cc_d)
                    if a != b != c:
                        s += gcd*6
                    else:
                        s += gcd*3
    print(s)
### BUGGY CODE ###

class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
      self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      
N,M=map(int,input().split())
List=[[int(i) for i in input().split()] for i in range(M)] 
wuf=WeightsUnionfind(N)
F=0
for l in List:
  wuf.unite(l[0]-1,l[1]-1,l[2])
for l in List:
  if wuf.weigh(l[1]-1)-wuf.weigh(l[0]-1)!=l[2]:
    F=1
    break
if F==1:
  print("No")
else:
  print("Yes")
    

  
      
    
      
      

### FIXED CODE ###

class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
          
N,M=map(int,input().split())
wuf=WeightsUnionfind(N)
F=0
for m in range(M):
  l,r,d=map(int,input().split())
  wuf.unite(l-1,r-1,d)
if wuf.wrong==1:
  print("No")
else:
  print("Yes")
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())

Anslist = np.ones(N) * K
check = np.array(range(N))

for i in range(Q):
    a = int(input())
    Anslist[check != a-1] -= 1

for i in range(N):
    if Anslist[i] > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K, Q = map(int, input().split())

Anslist = [0 for i in range(N)]
for _ in range(Q):
    a = int(input())
    Anslist[a-1] += 1

for i in range(N):
    if Anslist[i] > Q - K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import time,sys
start=time.time()
while time.time()-start<=4.979:pass
for input in sys.stdin:print(sum(map(int,input.split())))

### FIXED CODE ###

import time,sys
s=time.time()
while time.time()-s<=4.9775:pass
for i in sys.stdin:print(sum(map(int,i.split())))
### BUGGY CODE ###

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        i = 1
        while i * val <= 10 ** 6:
            dame_set.add(i * val)
            i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            while i * val <= 10 ** 6:
                dame_set.add(i * val)
                i += 1

print(ret)


### FIXED CODE ###

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        if val in dame_set:
            continue
        else:
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1

print(ret)