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

from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0

soin=defaultdict(int)
while m>=2:
    for i in range(2,int(n**.5)+5):
        while m%i==0 and m!=0:
            m//=i
            soin[i]+=1
            if m==1:
                break
                
L=list(soin.values())
ans=1
for l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0
def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f
# soin=defaultdict(int)
# while m>=2:
#     for i in range(2,int(n**.5)+5):
#         while m%i==0 and m!=0:
#             m//=i
#             soin[i]+=1
#             if m==1:
#                 break
     
L=list(fctr1(m))
ans=1
for a,l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)
### BUGGY CODE ###

import collections

n=int(input())
As=list(map(int,input().split()))
ls=collections.Counter(As)
subd={}
for i in As:
  l=ls.values()
  ans=0
  if i not in subd.keys():
    ls[i]=ls[i]-1
    for k in l:
      ans+=k*(k-1)//2
    subd[i]=ans
    ls[i]=ls[i]+1
  else:
    ans=subd[i]
  print(ans)

### FIXED CODE ###

import collections

n=int(input())
As=list(map(int,input().split()))
ls=collections.Counter(As)
subd={}
an=ls.values()
ans=0
for k in an:
  ans+=k*(k-1)//2
sans=ans

for i in As:
  ans=sans+1-ls[i]
  print(ans)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=sorted(nl())

s = [0]*(MAX)

for ai in a:
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  if s[ai]!=0:
    s[ai]=2
    continue
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

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

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


def main():
    dp = [0] * (S + 1)
    dp[0] = 1
    for i in range(N):
        dp, l = [0] * (S + 1), dp
        for j in range(S + 1):
            dp[j] = (dp[j] + 2 * l[j]) % MOD
            if A[i] + j <= S:
                dp[A[i] + j] = (dp[A[i] + j] + l[j]) % MOD
    
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


def main():
    dp = [0] * (S + 1)
    dp[0] = 1
    for i in range(N):
        dp, l = [0] * (S + 1), dp
        for j in range(S + 1):
            dp[j] = (dp[j] + 2 * l[j]) % MOD
            if A[i] + j <= S:
                dp[A[i] + j] = (dp[A[i] + j] + l[j]) % MOD
    
    ans = dp[-1]
    print(ans)


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

import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
for k in range(Q):
    c=0
    for n in range(l[k],r[k]+1,2):
        if P[n] and P[(n+1)//2]:
           c+=1
    print(c)


### FIXED CODE ###

import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])
### BUGGY CODE ###

class QuickFind(object):
    id=[]
    count=0
    
    def __init__(self,n):
        self.count = n
        i=0
        while i<n:
            self.id.append(i)
            i+=1
            
    def connected(self,p,q):
        return self.find(p) == self.find(q)

    def size(self,p):
        return len(list(filter(lambda x: self.id[x] == self.id[p], self.id)))
    
    def find(self,p):    
        return self.id[p]
    
    def union(self,p,q):
        idp = self.find(p)
        if not self.connected(p,q):
            for i in range(len(self.id)):
                if self.id[i]==idp:
                    self.id[i] = self.id[q] 
            self.count -= 1 

n, m = [int(x) for x in input().split()]
b = []
for i in range(m):
  b.append(tuple(int(x) - 1 for x in input().split()))
r = []
t = n*(n-1)//2
ds = QuickFind(n)
for i in range(m):
  q, p = b[-i-1]
  r.insert(0, t)
  if not ds.connected(p, q):
    t -= ds.size(p) * ds.size(q)
  ds.union(p, q)
for x in r:
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

from itertools import combinations

H, W, M = map(int, input().split())

bomb_h = [0] * H
bomb_w = [0] * W
grid = [[False] * W for _ in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    grid[h-1][w-1] = True

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if not grid[h][w]:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

H, W, M = map(int, input().split())

bomb_h = [0] * H
bomb_w = [0] * W
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    bomb.add((h-1, w-1))

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if (h, w) not in bomb:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

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

s = str(input())
s_bef = s
s_len = len(s)
for x in reversed(range(1, s_len)):
    s = s.replace("0" * x + "1" * x, "").replace("1" * x + "0" * x, "")

while len(s_bef) > len(s):
    s_bef, s = s, s.replace("01", "").replace("10", "")
 
print (s_len - len(s))

### FIXED CODE ###

s = str(input())
q = s[0]
for c in s[1:]:
    if len(q) >= 1:
        if q[-1] != c:
            q = q[:-1]
        else:
            q += c
    else:
        q += c
print(len(s) - len(q))
### BUGGY CODE ###

from math import factorial as f

N = int(input())
L = list(map(int,input().split()))
L = sorted(L,reverse=True)

def comb(a,b) :
    p = f(a)
    q = f(b)*f(a-b)
    return p//q

ANS = []
for i in range(N-1) :
    for j in range(i+1,N) :
        r = comb(L[i],L[j])
        ANS.append([r,L[i],L[j]])
ans = max(ANS)
print(ans[1],ans[2])


### FIXED CODE ###

from bisect import bisect_left as bl

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

p = L[-1]
q = bl(L,p/2)
if N == 2 :
    r = L[0]
else :
    if abs((p/2)-L[q]) < abs((p/2)-L[q-1]) :
        r = L[q]
    else :
        r = L[q-1]
print(p,r)
### BUGGY CODE ###

def main():
  import bisect
  A, B, Q = map(int, input().split())
  s = list()
  t = list()
  s.append(-10**12)
  t.append(-10**12)
  for i in range(A):
    s.append(int(input()))
  for i in range(B):
    t.append(int(input()))
  s.append(10**12)
  t.append(10**12)
  for i in range(Q):
    x = int(input())
    sw = bisect.bisect_right(s, x)-1 #xより西で一番近い(同じ場所でもいい)神社の番号
    se = sw + 1 #xより東で一番近い神社の番号
    tw = bisect.bisect_right(t, x)-1
    te = tw + 1
    l1 = max(x-s[sw], x-t[tw])
    l2 = max(s[se]-x, t[te]-x)
    l3 = s[se]-x + s[se]-t[tw]
    l4 = t[te]-x + t[te]-s[sw]
    l5 = x-s[sw] + t[te]-s[sw]
    l6 = x-t[tw] + s[se]-t[tw]
    print(min(l1, l2, l3, l4, l5, l6))
main()

### FIXED CODE ###

import bisect
INF = 10**15
A, B, Q = map(int, input().split())
s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]
for i in range(Q):
  x = int(input())
  sw = bisect.bisect_right(s, x)-1 #xより西で一番近い(同じ場所でもいい)神社の番号
  se = sw + 1 #xより東で一番近い神社の番号
  tw = bisect.bisect_right(t, x)-1
  te = tw + 1
  res = INF
  for S in [s[sw], s[se]]:
    for T in [t[tw], t[te]]:
      d1, d2 = abs(x-S) + abs(T-S), abs(x-T) + abs(S-T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

h,w=map(int,input().split())

M=[]
for i in range(h):
    M.append(input())

L=[]
for j in range(h):
    Lj=[]
    for i in range(w):
        if M[j][i]=="#":
            Lj.append(0)
        elif i==0:
            Lj.append(1)
        else:
            Lj.append(Lj[i-1]+1)
    L.append(Lj)
R=[]
for j in range(h):
    Rj=[]
    for i in range(w):
        if M[j][w-1-i]=="#":
            Rj.append(0)
        elif i==0:
            Rj.append(1)
        else:
            Rj.append(Rj[i-1]+1)
    R.append(Rj)   
U=[]
for i in range(w):
    Ui=[]
    for j in range(h):
        if M[j][i]=="#":
            Ui.append(0)
        elif j==0:
            Ui.append(1)
        else:
            Ui.append(Ui[j-1]+1)
    U.append(Ui)
D=[]
for i in range(w):
    Di=[]
    for j in range(h):
        if M[h-1-j][i]=="#":
            Di.append(0)
        elif j==0:
            Di.append(1)
        else:
            Di.append(Di[j-1]+1)
    D.append(Di)

s=0
for i in range(w):
    for j in range(h):
        s=max(s,L[j][i]+R[j][w-1-i]+U[i][j]+D[i][h-1-j]-3)

print(s)

### FIXED CODE ###

h,w=map(int,input().split())

M=[]
for i in range(h):
    M.append(input())

L=[]
for j in range(h):
    Lj=[]
    for i in range(w):
        if M[j][i]=="#":
            Lj.append(0)
        elif i==0:
            Lj.append(1)
        else:
            Lj.append(Lj[i-1]+1)
    L.append(Lj)
R=[]
for j in range(h):
    Rj=[]
    for i in range(w):
        if M[j][w-1-i]=="#":
            Rj.append(0)
        elif i==0:
            Rj.append(1)
        else:
            Rj.append(Rj[i-1]+1)
    R.append(Rj)   
U=[]
for i in range(w):
    Ui=[]
    for j in range(h):
        if M[j][i]=="#":
            Ui.append(0)
        elif j==0:
            Ui.append(1)
        else:
            Ui.append(Ui[j-1]+1)
    U.append(Ui)
D=[]
for i in range(w):
    Di=[]
    for j in range(h):
        if M[h-1-j][i]=="#":
            Di.append(0)
        elif j==0:
            Di.append(1)
        else:
            Di.append(Di[j-1]+1)
    D.append(Di)

s=0
for i in range(w):
    for j in range(h):
        s=max(s,L[j][i]+R[j][w-1-i]+U[i][j]+D[i][h-1-j]-3)

print(s)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

total = 0
for i in range(1,n+1):
    if i!=a and i!=b:
        total += cmb(n,i)

print(total)

### FIXED CODE ###

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

def comb(n,x):
    numerator = 1
    for i in range(n-x+1,n+1):
        numerator=  numerator * i  % mod
    
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    
    d = pow(denominator,mod-2,mod)

    return numerator * d

a = comb(n,a)
b =  comb(n,b)

print( (pow(2,n,mod) - 1  - a - b) %mod)
### BUGGY CODE ###

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

b = []

for i in range(n):
    b.append(a[i])
    b = b[::-1]

for i in range(n):
    print(b[i], end = " ")


### FIXED CODE ###

from collections import deque

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

b = deque()

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])

print(" ".join(map(str, b)))
### BUGGY CODE ###

import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if tb[now[0]][now[1]]:
            continue
        tb[now[0]][now[1]] = True
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj)-1)
                
print(ans)


### FIXED CODE ###

import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    tb[si][sj] = True
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]] and not tb[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
                tb[now[0]-1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1] and not tb[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
                tb[now[0]][now[1]+1] = True
                
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]] and not tb[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
                tb[now[0]+1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1] and not tb[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
                tb[now[0]][now[1]-1] = True
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj))
                
print(ans)
### BUGGY CODE ###

from math import gcd as gcd
K=int(input())

ans = 0

for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1), k+1)
print(ans)


### FIXED CODE ###

from math import gcd as gcd
K=int(input())

ans1 = 0
ans2 = 0
ans3 = 0

for i in range(K):
    for j in range(i+1,K):
        for k in range(j+1, K):
            ans1 += gcd(gcd(i+1,j+1), k+1)

for i in range(K):
    for j in range(i+1,K):
        ans2 += gcd(i+1,j+1)

for i in range(K):
    ans3+=i+1

print(ans1*6+ans2*6+ans3)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
# floor(a * x / b)
# = floor(a * floor(x / b) + a * (x / b - floor(x / b)))
# = a * floor(x / b) + floor(a * (x / b - floor(x / b))))
for i in range(min(b, n + 1)):
    ans = max(ans, int(a * i / b))
print(ans)


### FIXED CODE ###

a, b, n = map(int, input().split())
ans = 0
# floor(a * x / b)
# = floor(a * floor(x / b) + a * (x / b - floor(x / b)))
# = a * floor(x / b) + floor(a * (x / b - floor(x / b))))
print(int(a * min(b - 1, n) / b))
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

p("A ",A)

for i in range(M):
	b,c = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

	for j in range(b):
		if A[j]<c:
			A[j]=c
		else:
			break
	
	A.sort()
	p(b,c,A)


print(sum(A))





### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

p("A ",A)

B=[]
for i in range(M):
	b,c = map(int, input().split())
	B.append([b,c])


p("B ",B)
B=sorted(B, key=lambda x: x[1]*-1)
p("B ",B)


a=0
for i in range(len(B)):
	b = B[i]
	for j in range(b[0]):
		
		if A[a]<b[1]: A[a]=b[1]
		a+=1
		if a>=len(A): break

	if a>=len(A): break


print(sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
a=[[] for i in range(n)]
l=[0 for _ in range(n)]
ans=[0 for _ in range(n)]

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,input().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,input().split())
    l[t1-1]+=t2
dfs(-1,0,0)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

n,q = map(int,readline().split())
a=[[] for i in range(n)]
l=[0 for _ in range(n)]
ans=[0 for _ in range(n)]

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,readline().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,readline().split())
    l[t1-1]+=t2
dfs(-1,0,0)

print(" ".join(map(str,ans)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=((-1)**i_ct)*(2**(n-1-cond_ct))
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)

    ans = 0
    for i in range(n):
        num = 0
        for j in range(n):
            if i != j and a[i] % a[j] == 0:
                break
            if j == n - 1:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)

    max_a = max(a) + 1
    dp = [True] * max_a

    for idx in range(len(a)):
        if idx + 1 != len(a) and a[idx] == a[idx + 1]:
            dp[a[idx]] = False
        i = a[idx]
        x = 2
        while i * x < max_a:
            dp[i * x] = False
            x += 1

    ans = 0
    for i in a:
        if dp[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()