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

import math
import sys
input = sys.stdin.readline

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

    n = (2 * y - x) // 3
    m = y - 2 * n

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        ans = math.factorial(n+m) % mod
        ans = ans * modinv(math.factorial(n)) % mod
        ans = ans * modinv(math.factorial(m)) % mod
        print(ans)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

def main():
    mod = 10 ** 9 + 7
    x, y = map(int, input().split())
    if (2 * y - x) % 3 != 0:
        print(0)
        return None

    n = (2 * y - x) // 3
    m = y - 2 * n

    if n < 0 or m < 0:
        print(0)
    elif n == 0 and m == 0:
        print(0)
    elif n == 0 or m == 0:
        print(1)
    else:
        s = n + m + 1
        f = [1] * s

        for i in range(1, s):
            f[i] = f[i-1] * i % mod

        ans = f[n+m]
        ans = ans * modinv(f[n]) % mod
        ans = ans * modinv(f[m]) % mod
        print(ans)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now][1:]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[i] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

### FIXED CODE ###

from collections import deque

def bfs(graph, start):
    visited = {start: None}
    unvisited = deque()
    unvisited.append(start)
    while unvisited:
        now = unvisited.popleft()
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return visited

n, m = map(int, input().split())
g = [set() for i in range(n)]
group = []

for i in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    for j in range(len(group)):
        if s in group[j] and t in group[j]:
            print("yes")
            break
        elif s in group[j]:
            print("no")
            break
    else:
        group_tmp = set(bfs(g, s).keys())
        if t in group_tmp:
            print("yes")
        else:
            print("no")
        group.append(group_tmp)
### BUGGY CODE ###

n = int(input())
An = list(map(int, input().split()))
ans = An[0]
for i in range(1,n):
  if An[i] == 0:
    ans = 0
    break
  if An[i] > (10 ** 18):
    ans = -1
    break;
if ans > 0:
  ans = An[0]
  for i in range(1,n):
    if An[i] > (10 ** 18):
      ans = -1
      break
    ans *= An[i]
    if ans > (10 ** 18):
      ans = -1

print(str(ans))


### FIXED CODE ###

n = int(input())
An = list(map(int, input().split()))
An.sort(reverse=True)
ans = An[0]
for i in range(1,n):
  if An[i] == 0:
    ans = 0
    break
  if An[i] > (10 ** 18):
    ans = -1
    break;
if ans > 0:
  ans = An[0]
  for i in range(1,n):
    if An[i] > (10 ** 18):
      ans = -1
      break
    ans *= An[i]
    if ans > (10 ** 18):
      ans = -1
      break

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

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

import itertools

#n桁のm値のbitを生成
def bit(n, m):
    bit_list = list(itertools.product([i for i in range(m)], repeat=n))
    return bit_list

bts = bit(N, 2)

res = 0
for b in bts:
    tmp = 0
    for i in range(N):
        if b[i] == 0:
            tmp += V[i] - C[i]
            
    if tmp > res:
        res = tmp
        
print(res)
    

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

tmp = [0 for _ in range(N)]

for i in range(N):
    tmp[i] = V[i] - C[i]
  
res = 0
for i in range(N):
    if tmp[i] > 0:
        res += tmp[i]
            
        
print(res)
### BUGGY CODE ###

n,Y = map(int,input().split())
 
ans_x = -1
ans_y = -1
ans_z = -1
 
for x in range(n+1):
    for y in range(n+1):
        z = int((Y -10000*x - 5000*y)/1000)
        if z >= 0 and (z%1==0 or z==0) and x+y+z == n:
            ans_x = x
            ans_y = y
            ans_z = z
            break
 
print(ans_x, ans_y, ans_z)

### FIXED CODE ###

n,Y = map(int,input().split())
 
ans_x = -1
ans_y = -1
ans_z = -1
 
for x in range(n+1):
    for y in range(n+1-x):
        z = int((Y -10000*x - 5000*y)/1000)
        if z >= 0 and (z%1==0 or z==0) and x+y+z == n:
            ans_x = x
            ans_y = y
            ans_z = z
            break
 
print(ans_x, ans_y, ans_z)
### BUGGY CODE ###

def main():
    N_keta = int(input())
    S = input()

    total = 0

    for n in range(0, 1000):
        FLAG = False
        n_str = str(n)
        
        while (len(n_str) < 3):
            n_str = '0' + n_str
        
        pos = 0
        cnt = 0
        
        for i in range(3):
            number = int(n_str[i])
            
            while (pos < N_keta):
                num = int(S[pos])
                if (num == number):
                    cnt += 1
                    pos += 1
                    break
                else:
                    pos += 1
            
            if (cnt == 3):
                FLAG = True
                break
        
        if (FLAG):
            total += 1

    print(total)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N_keta = int(input())
    S = input()

    total = 0

    for n in range(0, 1000):
        FLAG = True
        n_str = "{:03}".format(n)
        pos = 0
        
        for i in n_str:
            numberS = S[pos:]
            if (i not in numberS):
                FLAG = False
                break
            else:
                pos += numberS.index(i) + 1
        
        if (FLAG):
            total += 1

    print(total)


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

n = int(input())
s = list(input())
ans = 0
for i in range(1,n):
    tmpans = 0
    streak = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            streak += 1
        else:
            tmpans = max(tmpans,min(i,streak))
            streak = 0
    tmpans = max(tmpans,min(i,streak))
    ans = max(tmpans,ans)
print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0
for i in range(1,n):
    tmpans = 0
    streak = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            streak += 1
        else:
            tmpans = max(tmpans,min(i,streak))
            streak = 0
    tmpans = max(tmpans,min(i,streak))
    ans = max(tmpans,ans)
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
r=s.count('R')
g=s.count('G')
b=s.count('B')
cnt=0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if (j-i == k-j) and (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
                cnt += 1
print(r*g*b-cnt)

### FIXED CODE ###

n=int(input())
s=input()
r=s.count('R')
g=s.count('G')
b=s.count('B')
cnt=0
for i in range(n-1):
    for j in range(1, min(i+1, n-i)):
            if (s[i] != s[i-j]) and (s[i] != s[i+j]) and (s[i-j] != s[i+j]):
                cnt += 1
print(r*g*b-cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def input_int_array():
    return map(int, input().split())


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1
    count[1] = -1

    for i in range(n):
        if i > 0:
            count[i] += count[i-1]
        for j in range(k):
            l, r = spans[j]
            r += 1
            if i + l < n:
                count[i + l] += count[i]
            if i + r < n:
                count[i + r] -= count[i]
    print(count[-1] % 998244353)


answer()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def input_int_array():
    return map(int, input().split())


MOD = 998244353


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0] * (n)
    count[0] = 1
    accum = [0] * (n + 1)
    accum[1] = 1

    for i in range(1, n):
        j = i + 1
        for l, r in spans:
            start = max(0, j - r - 1)
            end = max(0, j - l)
            count[i] += accum[end] - accum[start]
        accum[j] = accum[j-1] + count[i] % MOD
    print(count[n-1] % MOD)


answer()
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for x in range(1,n+1):
    f = (x / b - int(x / b))  
    if ans <= f:
        ans = f
print(int(ans * a))

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

from collections import defaultdict
S = input()
T = input()
D = defaultdict(list)
for i, s in enumerate(S):
  D[s].append(i + 1)
def bsearch(d, pos, loop):
  l = len(d)
  if l < 1:
    return -1, 0
  if pos < d[0]:
    return d[0], loop
  if d[l - 1] <= pos:
    loop += 1
    return d[0], loop
  low = 0
  high = l
  while high - low > 1:
    mid = (high - low) // 2
    if pos < d[mid]:
      high = mid
    else:
      low = mid
  return d[high], loop
pos = 0
loop = 0
for t in T:
  pos, loop = bsearch(D[t], pos, loop)
  if pos == -1:
    print(-1)
    break
else:
  print(len(S) * loop + pos)

### FIXED CODE ###

import bisect
S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
pos = 0
loop = 0
for t in T:
  n = ord(t) - 97
  if D[n] == []:
    print(-1)
    break
  _d = bisect.bisect(D[n], pos)
  _pos = D[n][_d % len(D[n])]
  if _pos <= pos:
    loop += 1
  pos = _pos
else:
  print(len(S) * loop + pos)
### BUGGY CODE ###

#import math
#gcd = math.gcd
from fractions import gcd



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

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

ans = 0
MOD = 10**9+7
cur = 1
for a in A:
    cur =  lcm(cur,a)
    
for a in A:
    ans += cur//a
    ans %= MOD
print(ans)



### FIXED CODE ###


from fractions import gcd


MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
#%%
def modinv(x,mod):
    return pow(x,mod-2,mod)

B = []
for a in A:
    b = modinv(a,MOD)
    B.append(b)

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

ans = 0

cur = 1
for a in A:
    cur =  lcm(cur,a)
for b in B:
    ans += cur*b
ans %= MOD
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, W = list(map(int, input().split()))
Z = []
for i in range(N):
    Z.append(list(map(int, input().split())))

dp = [[0] * (W+1) for _ in range(N+1)]

for i, z in enumerate(Z):
    #print(i)
    for w in range(W+1):
        if w -z[0] >= 0:
            dp[i+1][w] = max(dp[i][w-z[0]]+z[1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
    #print(dp)

print(max(dp[-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-

N, W = list(map(int, input().split()))
Z = []
for i in range(N):
    Z.append(list(map(int, input().split())))

dp = [[0] * (W+1) for _ in range(N+1)]

for i, z in enumerate(Z):
    #print(i)
    for w in range(W+1):
        if w -z[0] >= 0:
            dp[i+1][w] = max(dp[i][w-z[0]]+z[1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
    #print(dp)

print(max(dp[-1]))
### BUGGY CODE ###

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

N, M = map(int, input().split())
graph = [dict() for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
used_edge = set()
for i in range(N):
    di = Dijkstra(graph, i)

    for j in range(N):
        if i == j:
            continue
        di.goal_point = j
        path = di.execute()
        for p in range(len(path)-1):
            used_edge.add((path[p], path[p+1]))
            used_edge.add((path[p+1], path[p]))
print(M-len(used_edge)//2)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
N, M = map(int, input().split())

inf = float("inf")
graph = [[inf for _ in range(N)] for _ in range(N)]
edge = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    edge.append([a-1, b-1])
w_graph = floyd_warshall(graph)

count = 0
for e in edge:
    e_s = e[0]
    e_e = e[1]
    used = False
    for i in range(N):
        if w_graph[i][e_e] == w_graph[i][e_s] + graph[e_e][e_s]:
            used = True
    if not used:
        count += 1

print(count)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = a
#print(a)
for i in range(n):
  x = b.pop(i) #i番目の要素を削除
  print(max(b)) #その中での最大値を出力
  b.insert(i, x) #削除した要素を戻す

### FIXED CODE ###

import heapq

n = int(input())
a = [int(input()) for i in range(n)]
b = heapq.nlargest(2, set(a))
c = a.count(b[0])

if len(b) == 1 or c > 1: #bの長さが1または、最大値が2回以上存在するなら
    for i in range(n):
        print(b[0]) #最大値のみを表示

else: #bの長さが2以上なら
    for i in range(n):
        if a[i] == b[0]: #i番目が最大値だったら
            print(b[1]) #2番目に大きい値を出力
        else: #そうでなければ
            print(b[0]) #最大値を出力
### BUGGY CODE ###

from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    count = 0
    for i in range(n):
        for div in divisors[a[i]]:
            if (div in hm and (div!=a[i] or hm[a[i]]>1)) or ((a[i] // div in hm) and (div!=1 or hm[a[i]]>1)):
                count -= 1
                break
        count += 1
    print(count)
    return


def get_divisors():
    divisors = [[] for _ in range(10**6+1)]
    for i in range(1, 10**3+1):
        for j in range(i, 10**6+1, i):
            divisors[j].append(i)
    return divisors



n = RN()
a = RA()
hm = {}
for ai in a:
    if not ai in hm:
        hm[ai] = 0
    hm[ai] += 1
divisors = get_divisors()
solve()


### FIXED CODE ###

from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    count = 0
    for i in range(n):
        for div in divisors[a[i]]:
            if (div in hm and (div!=a[i] or hm[a[i]]>1)) or ((a[i] // div in hm) and (div!=1 or hm[a[i]]>1)):
                count -= 1
                break
        count += 1
    print(count)
    return


def get_divisors():
    divisors = [[] for _ in range(mxa+1)]
    for i in range(1, 10**3+1):
        for j in range(i, mxa+1, i):
            divisors[j].append(i)
    return divisors


n = RN()
a = RA()
mxa = max(a)
hm = {}
for ai in a:
    if not ai in hm:
        hm[ai] = 0
    hm[ai] += 1
divisors = get_divisors()
solve()
### BUGGY CODE ###

N, A, B = map(int, input().split())

if N == 1:
    if A == B:
        print(1)
    else:
        print(0)
elif A > B:
    print(0)
else:
    c = 0
    for _ in range(N-2):
        c += (B-A)
    print(c+1)


### FIXED CODE ###

N, A, B = map(int, input().split())

if N == 1:
    if A == B:
        print(1)
    else:
        print(0)
elif A > B:
    print(0)
else:
    print((B-A)*(N-2)+1)
### BUGGY CODE ###

# coding=utf-8


n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
C = 0

for i in range(q):
    if T[i] in S:
        C += 1
print(C)

### FIXED CODE ###

# coding=utf-8


n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
S = set(S)
T = set(T)

satisfied_set = S & T

C = len(satisfied_set)

print(C)
### BUGGY CODE ###

import bisect, math
N,D,A = map(int,input().split())
enemy = list(list(map(int,input().split()))for i in range(N))
enemy.sort()

damege = [0]*N

ans = 0
p = 0
while p < N:
    if p>=1:
        damege[p] += damege[p-1]
    enemy[p][1] -= damege[p]
    if enemy[p][1] <= 0:
        p += 1 
        continue
    d = math.ceil(enemy[p][1]/A)
    ans += d
    d *= A
    r = bisect.bisect_right(enemy,[enemy[p][0]+D*2,10**9+7])
    if r!=N:
        damege[r]-=d
    damege[p] += d
    p+=1
print(ans)



### FIXED CODE ###

import bisect, math
N,D,A = map(int,input().split())
enemy = list(list(map(int,input().split()))for i in range(N))
enemy.sort()

damege = [0]*N

ans = 0
p = 0
while p < N:
    if p>=1:
        damege[p] += damege[p-1]
    enemy[p][1] -= damege[p]
    if enemy[p][1] <= 0:
        p += 1 
        continue
    d = math.ceil(enemy[p][1]/A)
    ans += d
    d *= A
    r = bisect.bisect_right(enemy,[enemy[p][0]+D*2,10**9+7])
    if r!=N:
        damege[r]-=d
    damege[p] += d
    p+=1
print(ans)
### BUGGY CODE ###

n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 1
listh = list[h]
listhh = list[h-1]
th = int(listh[0])
thh = int(listhh[0])
ah = int(listh[1])
ahh = int(listhh[1])
while h < n:
     listh = list[h]
     listhh = list[h-1]
     th = int(listh[0])
     ah = int(listh[1])
     l = 1
     m = 1
     while l*th < thh:
        l += 1
     while m*ah < ahh:
        m += 1
     if l>m:
        thh = th*l       
        ahh = ah*l
     else:
        thh = th*m
        ahh = ah*m
     h += 1
print(thh+ahh)

### FIXED CODE ###

from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1.0
ah = 1.0

def f1(a,b):
     if a%b == 0:
          return a/b
     else:
          return a//b + 1

while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(f1(th,x),f1(ah,y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(int(th+ah))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__tour=[0]*(2*n-1)
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__tour[self.__k]=v
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__tour[self.__k]=v
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

    @property
    def tour(self):
        return self.__tour

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()
### BUGGY CODE ###

import math 
def factors(n):
    fact = []
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n / i == i):
                fact.append(i) 
            else:
                fact.append(i)
                fact.append(n // i)
        i = i + 1
    return fact
n = int(input())
l = list(map(int, input().split()))
vis = [0] * 1000003
ans = 0
for i in l: vis[i] -= -1
for i in range(n):
    tmp = factors(l[i])
    cnt = 0
    for j in tmp:
        cnt += vis[j]
        if j == l[i]: cnt += -1
    if cnt == 0: ans -= -1
print(ans)

### FIXED CODE ###

import os, sys, atexit
from io import BytesIO, StringIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER
 
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
l = list(map(int, input().split()))
l.sort()
vis = [0] * 1000004
for i in l: vis[i] -= -1
for i in range(n):
    tmp = l[i]
    while tmp <= l[n - 1]:
        if vis[tmp]:
            if tmp == l[i]:
                if vis[tmp] > 1: vis[tmp] = 0
            else:
                vis[tmp] = 0
        tmp += l[i]
ans = 0
for i in vis: ans += i
print(ans)