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

n,m=map(int,input().split())
i=2
s={}
while 1<m:
  j=0
  while m % (i**(j+1))==0:
    j+=1
  if j:
    m//=i**j
    s[i]=j
  i+=1
a=1
for v in s.values():
  c = 1
  for i in range(v):
    c = c * (n+i) // (1+i)
  a = a * c % (10**9+7)
print(a)


### FIXED CODE ###

n,m=map(int,input().split())
i=2
s=[]
while i*i<=m:
  j=0
  while m % i == 0:
    m//=i
    j+=1 
  if j:
    s+=[j]
  i+=1
a=1
if m > 1:
  s+=[1]
  
for v in s:
  c = 1
  for i in range(v):
    c = c * (n+i) // (1+i)
  a = a * c % (10**9+7)
print(a)
### BUGGY CODE ###

N = int(input())
ninzu = [int(input()) for i in range(5)]
cond = [N, 0, 0, 0, 0, 0]
flag = [0] * 6
cnt = 0
while cond[5] < N:
    if cond[0] >= ninzu[0]:
        flag[0] = 1
    else:
        flag[0] = 0
    if cond[1] >= ninzu[1]:
        flag[1] = 1
    else:
        flag[1] = 0
    if cond[2] >= ninzu[2]:
        flag[2] = 1
    else:
        flag[2] = 0
    if cond[3] >= ninzu[3]:
        flag[3] = 1
    else:
        flag[3] = 0
    if cond[4] >= ninzu[4]:
        flag[4] = 1
    else:
        flag[4] = 0
    for i in range(4, -1, -1):
        if flag[i]:
            cond[i + 1] += ninzu[i]
            cond[i] -= ninzu[i]
        else:
            cond[i + 1] += cond[i]
            cond[i] = 0
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
ninzu = [int(input()) for i in range(5)]
import math
min_ = min(ninzu)
a = math.ceil(N / min_)
print(a + 4)
### BUGGY CODE ###

import math
from functools import reduce

k = int(input().rstrip())

def gcd(numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                for c in range(1, k + 1):
                    if c == 1:
                        ans += 1
                    else:
                        ans += gcd([a, b, c])

print(ans)

### FIXED CODE ###

import math

k = int(input().rstrip())


ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                if a == b:
                    tmp = a
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)
                else:
                    tmp = math.gcd(a, b)
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)

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

n = int(input())

class Hash:
    def __init__(self):
        self.m = 1000003
        self.T = [None] * self.m
    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self.T[j] == None:
                self.T[j] = key
                break
            else:
                i = i + 1
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self.T[j] == key:
                return j
            elif self.T[j] == None:
                return None
            else:
                i += 1
        return self.T[self.h(key)]
    def h(self, key, i):
        ki = self.key2int(key)
        h1 = ki % self.m
        h2 = i * (1 + (ki % (self.m - 1)))
        return (h1 + h2) % self.m
    def key2int(self, key):
        p = 1
        ret = 0
        for s in key:
            a = ['A', 'C', 'G', 'T'].index(s) + 1
            ret += p * a
            p *= 5
        return ret

h = Hash()
for i in range(n):
    op, st = input().split()
    if op == 'insert':
        h.insert(st)
    else:
        if h.search(st):
            print('yes')
        else:
            print('no')

### FIXED CODE ###

n = int(input())
h = {}

for i in range(n):
    op, st = input().split()
    if op == 'insert':
        h[st] = 'yes'
    else:
        print (h.get(st, 'no'))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import gcd
from functools import reduce

def gcd_list(numlist):
    return reduce(gcd, numlist)

def main():
    K = int(input())

    s = 0

    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                s += gcd_list([a, b, c])
    
    print(s)



if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import gcd
from functools import reduce

def gcd_list(numlist):
    return reduce(gcd, numlist)

def main():
    K = int(input())

    s = 0

    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                s += gcd_list([a, b, c])
    
    print(s)



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

import sys
N,K = map(int,sys.stdin.readline().split())
h = list(map(int,input().split()))
dp = [0]+[float('inf') for a in range(N-1)]

for i in range(1,N):
  
  for j in range(max(0,i-K),i):
    dp[i] = min(dp[i],abs(h[i]-h[j])+dp[j])
    

print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

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

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
                break
        else:
            continue
print(len(sum_set))

### FIXED CODE ###

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

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)
### BUGGY CODE ###

n = int(input())
c = input()
c = list(c)
f = 0
ans = 0
while f == 0:
  if 'R' in c and 'W' in c:
    r = len(c) - c[::-1].index('R') - 1
    w = c.index('W')
    c[r] = 'W'
    c[w] = 'R'
    ans += 1
    for i, e in enumerate(c):
      if e == 'R':
        c[i] = ''
      else:
        c.remove('')
        break
  else:
    f = 1
    break
print(ans)

### FIXED CODE ###

n = int(input())
c = input()
c = list(c)
arr = []
a = 0
b = c.count('R')
arr.append(max(a, b))
for i in range(n):
  if c[i] == 'W':
    a += 1
  elif c[i] == 'R':
    b -= 1
  arr.append(max(a, b))
ans = min(arr)
print(ans)
### BUGGY CODE ###

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

b = []
for i in range(p):
    if a[i] ==  1:
        b.append(i)

ans = [0]*p

for i in range(0,p):
    for j in b:
        ans[p-1-i] -= pow(j,i,p)
    ans[p-1-i] %= p
 
ans[0] += -len(b)*(p-1)
ans[0] %= p

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

p = int(input())
a = [int(i) for i in input().split()]

ans = [0]*p

for i,j in enumerate(a):
    if j == 0:
        continue
    ans[0] -= p-1
    m = 1
    for k in range(p):
        ans[p-1-k] -= m
        ans[p-1-k] %= p
        m *= i
        m %= p

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

from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

inf = 10 ** 10
cost = [[inf] * w for _ in range(h)]

walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if [i, j] not in [[0, 0]] + walk]

q = deque()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

inf = 10 ** 10
cost = [[inf] * w for _ in range(h)]

walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if [i, j] not in [[0, 0]] + walk]

q = deque()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    a, b = map(int, input().split())
    B.append(a)
    C.append(b)
d = collections.Counter(A)
ans = 0
c = list(d.keys())
cs = list(d.values())
for i in range(Q):
    l=[j for j,x in enumerate(c) if x == B[i]]

    for k in l:
        c[k]=C[i]
    for m in range(len(c)):
        ans += c[m]*cs[m]
    print(ans)
    ans = 0


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

for i in range(q):
    s += (c[i]-b[i])*num[b[i]]
    num[c[i]] += num[b[i]]
    num[b[i]] = 0
    print(s)
### BUGGY CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append((r,l,i))

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for r,l,i in qi:
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        if bq_al[r] == 0:
            bq_al[r] = BIT_query(r)

        ans[i] = bq_al[r]-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*((10**6+1)**2)+l*(10**6+1)+i)

    qi.sort()

    ans = [0]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%(10**6+1)
        l = (ist//(10**6+1))%(10**6+1)
        r = ist//(10**6+1)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)


    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()
### BUGGY CODE ###

import numpy as np

def solve(stdin):
    n = stdin[0]
    dp = np.zeros(n+1,dtype=np.int64)
    for i in range(1,n+1):
        for j in range(i,n+1,i):
            dp[j]+=1
    dp*=np.arange(n+1)
    return dp.sum()

def main():
    stdin = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
    print(solve(stdin))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    #from my_module import solve
    main()

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    ans+=n//i*(n//i+1)//2*i
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = 1
ans=[]
for i in range(k):
    s *= a[i]
ans.append(s)
for i in range(k, n):
    s = s * a[i] // a[i - k]
    ans.append(s)
    if ans[i - k] < ans[i - k + 1]:
        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 ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            assert cpN != 0
            assert n != 0
            if cpN % n == 0:
                cpN //= n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        loop = 0
        while True:
            loop += 1
            if loop > 100:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()
### BUGGY CODE ###

n, k  = map(int, input().split())
L = list(map(int, input().split()))
E = []
for i in range(len(L)):
  E.append((1+L[i])/2)
S = []  
for i in range(len(E)-k+1):
  sum = E[i]
  for j in range(1, k):
    sum += E[i+j]
  S.append(sum)
print(max(S)) 

### FIXED CODE ###

n, k  = map(int, input().split())
L = list(map(int, input().split()))
E = []
for i in range(len(L)):
  E.append((1+L[i])/2)
v = 0
for i in range(k):
  v += E[i]
S = [v]  
for i in range(k, len(E)):
  v = v + E[i] - E[i-k]
  S.append(v)
print(max(S))
### BUGGY CODE ###

_MULTITEST = False
##
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    neg = [x for x in a if x < 0]
    pos = [x for x in a if x > 0]
    zeroes = a.count(0)
    #
    neg.sort()
    pos.sort()
    
    ### Set lower bound for answer
    ans = 0
    if len(pos) == 0:
        if zeroes == 0:
            ans = -1 * (10**16)
    
    ### Solve by window-sliding
    # set some initial vars
    prod = 1
    zero_counter = 0
    for i in range(n-1, n-1-k, -1):
        if a[i] == 0:
            zero_counter += 1
        else:
            prod *= a[i]
    if zero_counter > 0:
        ans = max(ans, 0)
    else:
        ans = max(ans, prod)
    
    # sliding
    p1 = 0
    p2 = (n-k)
    while p2 < n:
        if a[p1] == 0:
            zero_counter += 1
        else:
            prod *= a[p1]
        if a[p2] == 0:
            zero_counter -= 1
        else:
            prod //= a[p2]
        p1 += 1; p2 += 1;
        if zero_counter > 0:
            ans = max(ans, 0)
        else:
            ans = max(ans, prod)
    
    ###
    #print(ans)
    print(ans % (10**9 + 7))


##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

### FIXED CODE ###

_MULTITEST = False
##
def solve():
    MOD = int(1e9) + 7

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

    neg = sum(1 for x in a if x < 0)
    pos = sum(1 for x in a if x > 0)
    zero = a.count(0)
    
    ### Set lower bound for answer
    ans_is_neg = False
    if n == k:
        if zero == 0 and neg % 2 == 1:
            ans_is_neg = True
    else:
        if pos == 0:
            if zero == 0:
                if k % 2 == 1:
                    ans_is_neg = True
    
    ### Solve by window-sliding
    # set some initial vars

    #print(ans_is_neg)
    if ans_is_neg:
        prod = 1
        for i in a[n-k:n]:
            prod = (prod * i) % MOD
        print(prod)
    else:
        prod = 1
        p1 = 0; p2 = n-1;
        while k > 0:
            if k > 1 and p1 + 1 < n and 0 < p2 and a[p1] * a[p1+1] > a[p2] * a[p2-1]:
                prod = (prod * a[p1] * a[p1 + 1]) % MOD
                p1 += 2; k -= 2;
            else:
                prod = (prod * a[p2]) % MOD
                p2 -= 1; k -= 1;
        print(prod)

##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()
### BUGGY CODE ###

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


def lcm(X, Y):
    x = X
    y = Y
    if y > x:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return X*Y//y


l = 1

mod = pow(10, 9) + 7


for i in list(a):
    l = lcm(l, i)

ans = 0

for i in list(a):
    ans += l // i
    ans %= mod

print(ans)


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

cnt=0
ans=0
LCM=1
for i in range(n):
    Q=lcm(LCM,A[i])
    cnt*=Q//LCM
    LCM=Q
    cnt+=Q//A[i]
print(cnt%mod)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, d, a = map(int, input().strip().split())
  XsHs = [list(map(int, input().strip().split())) for _ in range(n)]
  XsHs.sort(key = lambda x:x[0])

  queue = list()
  total = 0
  ans = 0
  for x, h in XsHs:
    while True:
      if len(queue) != 0 and queue[0][0] < x:
        total -= queue[0][1]
        del queue[0]
      else:
        break
    h -= total
    if h > 0:
      num = (h+a-1)//a
      ans += num
      total += (num*a)
      queue.append((x+(2*d), num*a))
  print(ans)

if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import deque

def main():
  n, d, a = map(int, input().strip().split())
  XsHs = [list(map(int, input().strip().split())) for _ in range(n)]
  XsHs.sort(key = lambda x:x[0])

  queue = deque()
  total = 0
  ans = 0
  for x, h in XsHs:
    while queue:
      if queue[0][0] < x:
        total -= queue[0][1]
        queue.popleft()
      else:
        break
    h -= total
    if h > 0:
      num = (h+a-1)//a
      ans += num
      total += (num*a)
      queue.append((x+(2*d), num*a))
  print(ans)

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

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	Acnt = Counter(A)
	if 1 in Acnt:
		print(1 if Acnt[1] == 1 else 0)
		return
	ans = 0
	for i, num in enumerate(A):
		div = 2
		flag = True
		if Acnt[num] > 1:
			continue
		while div*div <= num:
			if num % div == 0:
				other = num//div
				if div in Acnt or other in Acnt:
					flag = False
					break
			div += 1
		if flag:
			ans += 1
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	indices = defaultdict(lambda: [])
	Amax = NINF
	if 1 in indices:
		print(1 if len(indices[1]) == 1 else 0)
		return
	A.sort()	
	for i, num in enumerate(A):
		indices[num].append(i)
		Amax = max(Amax, num)
	set_false = set()
	dp = [1 for _ in range(n)]
	for i, num in enumerate(A):
		if i in set_false: continue
		if len(indices[num]) > 1:
			dp[i] = 0
		curr = num
		while curr <= Amax:
			for j in indices[curr]:
				if i == j: continue
				dp[j] = 0
				set_false.add(j)
			curr += num
	print(sum(dp))
	stdout.close()

if __name__ == "__main__":
	main()