CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import random
input = sys.stdin.readline
n = int(eval(input()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
degorigin = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  degorigin[a] += 1
  degorigin[b] += 1
if n == 2:
  print("Second")
  exit()
stackorigin = []
root = 0
candidate = []
for i in range(1,n+1)[::-1]:
  if degorigin[i] == 1:
    stackorigin.append(i)
  else:
    candidate.append(i)
flg = 0
for _ in range(18):
  if flg:
    break
  stack = stackorigin[:]
  deg = degorigin[:]
  root = candidate[random.randint(0,len(candidate)-1)]
  deg[root] += 1
  dp = [[] for i in range(n+1)]
  parity = [-1]*(n+1)
  while stack:
    x = stack.pop()
    if dp[x]:
      if dp[x].count(0) >= 2:
        flg = 1
        break
      elif dp[x].count(2):
        parity[x] = 2
      elif dp[x].count(1) and dp[x].count(0):
        parity[x] = 2
      elif dp[x].count(1):
        parity[x] = 0
      elif dp[x].count(0):
        parity[x] = 1
    else:
      parity[x] = 0
    for y in graph[x]:
      if deg[y] >= 2:
        dp[y].append(parity[x])
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
if flg:
  print("First")
else:
  print("Second")

# Optimized solution

import sys
input = sys.stdin.readline
n = int(eval(input()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
if n == 2:
  print("Second")
  exit()
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    root = i
flg = 0
deg[root] += 1
dp = [[] for i in range(n+1)]
dist = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0)>=2:
      flg = 1
    if dp[x].count(0):
      dist[x] = 1
    else:
      dist[x] = 0
  else:
    dist[x] = 0
  for y in graph[x]:
    if deg[y] >= 2:
      dp[y].append(dist[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg or dist[root]==0:
  print("First")
else:
  print("Second")
# Original solution
a=int(eval(input()))
b=list(map(int,input().split()))
c=max(b)+1
d=[]
ans=0
for i in range(a):
  e=0
  while c-e>b[i]:
    e+=b[i]
    d+=[e]
for i in b:
    if d.count(i)==1:
      ans+=1
print(ans)

# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print((sum(cnt_d[ai] == 1 for ai in a)))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
check = [0] * 1000001
res = 0
for i in range(N):
    if not check[A[i]] and (i == N-1 or A[i] != A[i+1]):
        res += 1
    for j in range(A[i], 1000001, A[i]):
        check[j] = 1
print(res)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
check = [0] * 1000001
res = 0
for i in range(N):
    if check[A[i]]:
        continue
    if i == N-1 or A[i] != A[i+1]:
        res += 1
    for j in range(A[i], 1000001, A[i]):
        check[j] = 1
print(res)
# Original solution

import collections
from copy import copy


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def f(n):
    facs = factorization(n)
    res = set()

    def g(arr, total):
        if len(arr) == 0:
            res.add(total)
            return

        a, b = arr.pop()
        for i in range(0, b + 1):
            num = a ** i
            res.add(num)
            g(copy(arr), total * num)

    g(facs, 1)

    return res


def main():
    n = int(eval(input()))
    A = tuple(map(int, input().split()))
    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    ans = n
    for i in range(n):
        a = A[i]

        if D[a] > 1:
            ans -= 1
            continue

        if a == 1:
            continue

        res = f(a)
        res.remove(a)
        for num in res:
            if num in D:
                ans -= 1
                break

    print(ans)


main()


# Optimized solution

import collections

def main():
    n = int(eval(input()))
    A = sorted(map(int, input().split()))

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()
# Original solution
N = int(eval(input()))
nokori = N
kaburi = set()
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A2 = set()
for i in A:
    if i in A2:
        kaburi.add(i)
    else:
        A2.add(i)
for i in kaburi:
    A2.remove(i)
for i in kaburi:
    k = i * 2
    while k < 1000000:
        A2.discard(k)
        k += i
while len(A2) != 0:
    i = min(A2)
    ans += 1
    k = i
    while k < 1000000:
        A2.discard(k)
        k += i
print(ans)

# Optimized solution
N = int(eval(input()))
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A.sort()
A2 = [True for i in range(A[-1] + 1)]
for i in range(len(A)):
    k = A[i] * 2
    if A2[A[i]]:
        if i != 0 and A[i-1] == A[i]:
            A2[A[i]] = False
        while(k < len(A2)):
            A2[k] = False
            k += A[i]
for i in A:
    if A2[i]:
        ans += 1
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
if n!=1 and len(set(a))==1:
  print((0))
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
if n!=1 and min(a)>max(a)/2:
  ct=0
  for i in range(len(l)):
    if l[i]==1:
      ct+=1
  print(ct)
  exit()
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
T = set()
def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in A:
    T.add(x)
cnt = 0
maxi = max(A)
for x in sorted(A):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
ans = 0
for x in T:
    if c[x] == 1:
        ans += 1
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
T = set()

for x in A: T.add(x)

maxi = max(A)

for x in sorted(A):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
ans = 0

def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in T:
    if c[x] == 1:
        ans += 1
print(ans)
# Original solution
N = 1000001
a = [0]* N
eval(input())
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print((a.count(1)))


# Optimized solution
N = 1000001
a = [0]* N
eval(input())
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print((a.count(1)))
# Original solution
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print((a.count(1)))


# Optimized solution
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print((a.count(1)))
# Original solution
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print((a.count(1)))


# Optimized solution
N = 1000001
a = [0]* N
eval(input())
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print((a.count(1)))
# Original solution
n=int(eval(input()))
A=sorted(list(map(int,input().split())))
B=[0]*(1+max(A))
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,max(A)+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)

# Optimized solution
n=int(eval(input()))
A=sorted(list(map(int,input().split())))
B=[0]*(1+A[-1])
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,A[-1]+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)
# Original solution
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return list(map(int,input().split()))
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(eval(input()))
a=sorted(lmp())
c=[0]*M
for j in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
s=Counter(a).most_common()
for x,y in s:
    if c[x]==0 and y==1:
        ans+=1
print(ans)

# Optimized solution
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return list(map(int,input().split()))
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(eval(input()))
a=Counter(lmp()).most_common()
a=sorted(a, key=lambda x: x[0])
c=[0]*M
for j,x in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
for x,y in a:
    if c[x]==0 and y==1:
        ans+=1
print(ans)
# Original solution
inf =  1100000
def main():
  N =  int(eval(input()))
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for x in a:
    if detect[x] != 0:
      detect[x] = 2
    for i in range(x, inf, x):
      detect[i] += 1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

# Optimized solution
inf =  1100000
def main():
  N =  int(eval(input()))
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for x in a:
    if detect[x] != 0:
      detect[x] = 2
      continue
    for i in range(x, inf, x):
      detect[i] += 1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()
# Original solution
N =eval(input())
A = list(map(int, input().split()))
MA =max(A)
N=int(N)
s=0
A2 = [-1] 
B =[-1]#重複
LS =[-1]
for i in range(0,N):
  k=1
  P =A[i]
  if P in A2:
    B.append(P)
    pass
  else:
    while P*k<=MA:
      LS.append(P*k)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in B:
    pass
  else:
    if LS.count(A[j]) ==1:
      s=s+1

print(s)
    


# Optimized solution
N = eval(input())
A = list(map(int, input().split()))
N = int(N)
MA = max(A)
s=0
LS = [0 for i in range(0,MA)]
for i in range(0,N):
  k=1
  while A[i]*k<=MA:
    LS[A[i]*k-1] +=1
    k +=1
for j in range(0,N):
  if LS[A[j]-1]==1:
    s+=1
print(s)
# Original solution
import sys 
import math

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()
# print(A)

ans = 0 
invalid = set()
for i in range(N):
    if A[i] in invalid:
        continue

    flag = True
    for j in range(i+1, N):
        if A[j] in invalid:
            continue
        
        # print(A[i], A[j])
        if A[j] % A[i] == 0:
            invalid.add(A[j])
        if A[i] == A[j]:
            # print("break")
            #break
            flag = False
    else:
        if flag:
            ans += 1

print(ans)

# Optimized solution
import sys 

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()

max_a = max(A)
counts = [0 for _ in range(max_a + 1)]
ans = 0

for a in A:
    counts[a] += 1

for a in A:
    if counts[a] == 1:
        ans += 1
    n = 1
    while n * a <= max_a:
        counts[n * a] += 2
        n += 1

print(ans)
# Original solution
N = int(eval(input()))
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[N-1]

is_prime = [True] * (A_max+1)
is_prime[0] = False

for i in range(1, A_max):
    if i not in A_list:
        is_prime[i] = False


for i in A_list:
    if not is_prime[i]:
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    if A_list.count(i) >= 2:
        is_prime[i] = False

print((is_prime.count(True)))


# Optimized solution
N = int(eval(input()))
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[N-1]

is_prime = [False] * (A_max+1)


for i in A_list:
    is_prime[i] = True

x = -1
for i in A_list:
    if not is_prime[i]:
        continue
    elif x == i:
        is_prime[i] = False
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    x = i

count = 0
for i in A_list:
    if is_prime[i]:
        count += 1


print(count)
# Original solution
from collections import defaultdict
N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted(A)

divisible = [False for _ in range(int(1e6+1))]
cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
    if divisible[a] == False:
        for i in range(a+a, len(divisible), a):
            divisible[i] = True
ans = 0
for a in A:
    if divisible[a] is False and cnt[a] <= 1:
        ans += 1
print(ans)


# Optimized solution
from collections import defaultdict
N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted(A)

divisible = [False for _ in range(int(1e6+1))]
cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
    if divisible[a] == False and cnt[a] <= 1:
        for i in range(a+a, len(divisible), a):
            divisible[i] = True
ans = 0
for a in A:
    if divisible[a] is False and cnt[a] <= 1:
        ans += 1
print(ans)
# Original solution
n = int(eval(input()))
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    for j in range(m):
        if (j + 1) % i == 0:
            x[j] += 1

for i in ints:
    if x[i-1] == 1:
        cnt += 1

print(cnt)


# Optimized solution
n = int(eval(input()))
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    if x[i-1] >= 2:
        continue
    for j in range(m // i):

        x[i * (j + 1) - 1] += 1

for i in ints:
    if x[i - 1] == 1:
        cnt += 1

print(cnt)
# Original solution
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

nums = [0] * (10 ** 6 + 5)

for a in A:
    nums[a] += 1

MAX = 10 ** 6 + 1
pr = set()
for a in A:
    nums[a] -= 1
    b = a
    while b <= MAX:
        if nums[b] > 0:
            pr.add(b)
        b += a
    nums[a] += 1

ans = len(A)
for a in A:
    if a in pr:
        ans -= 1
# print(pr)
print(ans)






# Optimized solution
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

amax = max(A)
dp = [True] * (amax + 1)
count = [0] * (amax + 1)

for a in A:
    count[a] += 1
    b = 2 * a
    while b <= amax:
        dp[b] = False
        b += a

ans = 0
for a in A:
    if count[a] > 1:
        continue
    if dp[a]:
        ans += 1
print(ans)
# Original solution
def gcd(a, b):
    while b: a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                                                                                     31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p] + 1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)


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

X = [0] * (ma + 1)
Ans = [True] * (ma + 1)
ans = 0
A.sort()

for a in A:
    X[a] += 1
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
ma = max(A)

X = [0] * (ma + 1)
ans = 0
A.sort()

for a in A:
    X[a] += 1
for a in A:
    if X[a] ==1:
        ans += 1
    num = 1
    while num * a <= ma:
        X[num * a] += 2
        num += 1

print(ans)
# Original solution
from collections import deque

n = int(eval(input()))
a = list(map(int, input().split()))
a.sort(reverse=True)
d = deque(a)

cnt = 0
while len(d) > 0:
    dd = d.pop()
    flg = 0
    for i in reversed(list(range(len(d)))):
        if d[i] == dd:
            del d[i]
            flg = 1
        elif d[i] % dd == 0:
            del d[i]
    if flg == 0:
        cnt = cnt + 1


print(cnt)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
a_max=max(a)

check = [0]*(a_max+1)

for i in a:
    if check[i] != 0:
        check[i] = 2
        continue
    if check[i] == 0:
        check[i] = 1
        for j in range(1,a_max//i):
            check[(j+1)*i] = 2

print((check.count(1)))
# Original solution
N = int(eval(input()))
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    while x < leng:
        memo[x] +=1
        x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)

# Optimized solution
N = int(eval(input()))
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    if memo[n] >1:
        pass
    else:
        while x < leng:
            memo[x] +=1
            x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)

    return list(set(D))


count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1

print(count)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()

A_max = max(A)
dp = [True] * (A_max + 1)
count = 0
A_f = {a: 0 for a in A}
for a in A:
    A_f[a] += 1

for a in A:
    if dp[a]:
        for i in range(1, A_max + 1):
            if a * i > A_max:
                break
            dp[a * i] = False
        if A_f[a] == 1:
            count += 1

print(count)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
 
def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)
 
    return list(set(D))
 
 
count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1
 
print(count)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()

A_max = max(A)
dp = [True] * (A_max + 1)
count = 0
A_f = {a: 0 for a in A}
for a in A:
    A_f[a] += 1

for a in A:
    if dp[a]:
        for i in range(1, A_max + 1):
            if a * i > A_max:
                break
            dp[a * i] = False
        if A_f[a] == 1:
            count += 1

print(count)
# Original solution
from collections import Counter


def solve(string):
    n, *a = list(map(int, string.split()))
    table = [True] * (10**6 + 1)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, max(a) + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in list(Counter(a).items()) if v == 1))


if __name__ == '__main__':
    import sys
    print((solve(sys.stdin.read().strip())))


# Optimized solution
from collections import Counter


def solve(string):
    n, *a = list(map(int, string.split()))
    table = [True] * (10**6 + 1)
    ma = max(a)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, ma + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in list(Counter(a).items()) if v == 1))


if __name__ == '__main__':
    import sys
    print((solve(sys.stdin.read().strip())))