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

gcd_d = {}
import math

K = int(input())

ans_sum = 0
for ai in range(1, K + 1):
  for bi in range(1, K + 1):
    t_ab = tuple([ai, bi] if ai <= bi else [bi, ai])
    if t_ab not in gcd_d:
      gcd_d[t_ab] = math.gcd(ai, bi)
    gcd_ab = gcd_d[t_ab]
    for ci in range(1, K + 1):
      t_abc = tuple([gcd_ab, ci] if gcd_ab <= ci else [ci, gcd_ab])
      if t_abc not in gcd_d:
        gcd_d[t_abc] = math.gcd(gcd_ab, ci)
      ans_sum += gcd_d[t_abc]

print(ans_sum)

### FIXED CODE ###


from math import gcd

K = int(input())

a = 0
for ai in range(1, K + 1):
  for bi in range(1, K + 1):
    gcd_ab = gcd(ai, bi)
    for ci in range(1, K + 1):
      a += gcd(gcd_ab, ci)

print(a)
### BUGGY CODE ###

import collections
import math


def combinations_count(n, r):
    return (n*(n-1)//2)
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
Ay = list(set(A))
c = collections.Counter(A)
cnt = 0
ansx = []
ansy = []
ansy2 = []


for x, y in c.items():
    ansy.append(combinations_count(y, 2))
    # ansy2.append(combinations_count(y - 1, 2))
    ansx.append(x)
sumall = sum(ansy)

for i in A:
    print(sumall - A.count(i) + 1)


### FIXED CODE ###

import collections
import math

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


sumall = 0
for x, y in c.items():
    sumall += (y*(y-1)//2)

for i in range(N):
    print(sumall - c[A[i]] + 1)
### BUGGY CODE ###

# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np
# import heapq
# import array


def main():
    n = int(sys.stdin.readline().rstrip())

    sorted_letters = []
    count = 0
    for _ in range(n):
        s = ''.join(sorted(sys.stdin.readline().rstrip()))
        count += bi_r(sorted_letters, s) - bi_l(sorted_letters, s)
        in_l(sorted_letters, s)
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
from functools import reduce
import operator as op
# from scipy.misc import comb # float
# import numpy as np
# import heapq
# import array


def nCr(n, r):
    r = min(r, n - r)
    upper = reduce(op.mul, range(n, n-r, -1), 1)
    lower = reduce(op.mul, range(r, 0, -1), 1)
    return upper // lower

def main():
    n = int(sys.stdin.readline().rstrip())

    sorted_letters = [''.join(sorted(sys.stdin.readline().rstrip())) for _ in range(n)]
  
    count = 0
    for c in collections.Counter(sorted_letters).values():
        if c >= 2:
            count += nCr(c, 2)
            
    print(count)


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

N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

b = [(-1 if x in a else 0) for x in range(N+1)]

b[0] = 1

mod = 10**9+7
for i in range(1,N+1):
    if b[i] == -1:
        continue
    if i == 1:
        b[i] = b[0]
    else:
        b[i] = max(b[i-1],0) + max(b[i-2],0)
    b[i] %= mod

print(b[N])

### FIXED CODE ###

from collections import Counter

N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

c = Counter(a).keys()

b = [(-1 if x in c else 0) for x in range(N+1)]

b[0] = 1

mod = 10**9+7
for i in range(1,N+1):
    if b[i] == -1:
        continue
    if i == 1:
        b[i] = b[0]
    else:
        b[i] = max(b[i-1],0) + max(b[i-2],0)
    b[i] %= mod

print(b[N])
### BUGGY CODE ###

def add(bit):
    _list = list(reversed(format(bit, 'b')))
    for i in range(len(_list)):
        digit[i] += int(_list[i])
def diff(bit):
    _list = list(reversed(format(bit, 'b')))
    for i in range(len(_list)):
        digit[i] -= int(_list[i])
def evaluate():
    for _digit in digit:
        if _digit > 1:
            return False
    return True
def func(n, a):
    count = 0
    i = 0
    j = 0
    while j < n:
        while j < n:
            add(a[j])
            if evaluate():
                count += j - i + 1
                # print("j i:{} j:{} count:{} digit:{}".format(i, j, count, digit))
                j += 1
            else:
                break
        while i < j < n:
            diff(a[i])
            i += 1
            if evaluate():
                count += j - i + 1
                # print("i i:{} j:{} count:{} digit:{}".format(i, j, count, digit))
                break
        j += 1
    return count
"""
digit = [0 for _ in range(21)]
print(func(4, [2, 5, 4, 6]))
digit = [0 for _ in range(21)]
print(func(9, [0, 0, 0, 0, 0, 0, 0, 0, 0]))
digit = [0 for _ in range(21)]
print(func(19,[885, 8, 1, 128, 83, 32, 256, 206, 639, 16, 4, 128, 689, 32, 8, 64, 885, 969, 1]))
"""
digit = [0 for _ in range(21)]
n = int(input())
a = [int(i) for i in input().split()]
print(func(n, a))

### FIXED CODE ###

def evaluate(digit):
    _digit = str(format(digit, "b"))
    print(_digit)
    for i in range(len(_digit)):
        if int(_digit[i]) > 1:
            return False
    return True

def func(n, a):
    digit = 0
    count = 0
    i = 0
    j = 0
    while j < n:
        while j < n:
            if digit ^ a[j] == digit + a[j]:
                digit += a[j]
                count += j - i + 1
                # print("j i:{} j:{} count:{} digit:{}".format(i, j, count, format(digit, "b")))
                j += 1
            else:
                break
        while i < j < n:
            digit ^= a[i]
            i += 1
            break
        # print("_ i:{} j:{} count:{} digit:{}".format(i, j, count, format(digit, "b")))
    return count
"""
print(func(4, [2, 5, 4, 6]))
print(func(9, [0, 0, 0, 0, 0, 0, 0, 0, 0]))
print(func(19,[885, 8, 1, 128, 83, 32, 256, 206, 639, 16, 4, 128, 689, 32, 8, 64, 885, 969, 1]))
"""
digit = 0
n = int(input())
a = [int(i) for i in input().split()]
print(func(n, a))
### BUGGY CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}

for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(dics.values()))
while len(sortv) > k:
    kesu = kesu + sortv[0]
    sortv.remove(sortv[0])
print(kesu)

### FIXED CODE ###

n, k = map(int,input().split())
al = list(map(int,input().split()))
dics = {}
 
for i in range(n):
    if al[i] in dics:
        dics[al[i]] = dics[al[i]] + 1
    else:
        dics.update({al[i]:1})
        
counts = len(dics.values())
kesu = 0
sortv = list(sorted(list((dics.values()))))

i = counts
j = 0
while i > k:
    kesu = kesu + sortv[j]
    i = i - 1
    j = j + 1
print(kesu)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
g = []
ans = 0
for j in range(60):
    d = 0
    for i in range(n):
        if a[i]&1:
            d += 1
        a[i] >>= 1
    g.append(d)
for i in range(60):
    ans += g[i]*(n-g[i])*(pow(2,i,10**9+7))
    ans = ans % (10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

N,K = map(int, input().split())
x = list(map(int, input().split()))
ans = 0
for i in range(N-K+1):
    light = x[i:i+K]
    l = light[0]
    r = light[-1]
    time = min(abs(l)+abs(l-r), abs(r)+abs(r-l))
    if ans == 0 or time < ans:
        ans = time
print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
x = list(map(int, input().split()))
ans=min([min(abs(x[i])+abs(x[i]-x[i+K-1]),abs(x[i+K-1])+abs(x[i+K-1]-x[i])) for i in range(N-K+1)])
print(ans)
### BUGGY CODE ###

#!python3

import sys
from functools import reduce
from operator import or_
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 1, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        sd = S1[i] = defaultdict(int)
        i1 = i * nn
        for j in range(i1, min(N, i1+nn)):
            sd[S[j]] += 1

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c1 = S[i]
            i1 = i // nn
            S1[i1][c1] -= 1
            S[i] = j
            S1[i1][j] += 1
        elif cmd == "2":
            j = int(j)

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set(k for i1 in range(ia, ja) for k, v in S1[i1].items() if v > 0)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

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

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

mod=10**9+7
ans=0

for i in range(60):
    a=b=0
    for x in A:
        if x>>i&1:
            a+=1
        else:
            b+=1
    ans+=(a*b%mod)*pow(2,i,mod)
    ans%=mod

    
print(ans)

### FIXED CODE ###

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

mod=10**9+7
ans=0
cnt=[[0]*2 for _ in range(60)]

for x in A:
    for i in range(60):
        a=x%2
        x//=2
        cnt[i][a]+=1

for p,q in enumerate(cnt):
    i,j=q
    ans+=((i*j)%mod)*pow(2,p,mod)
    ans%=mod
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

AB.sort()


result = []

count = 0
for a,b in AB:
    min_k = min(b,K)
    result += [a]*min_k
    count += min_k
    if count >= K:
        break

print(result[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

AB.sort()

result = 0
for a,b in AB:
    K -= b
    result = a
    if K <= 0:
        break

print(result)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*((2**i))%(10**9+7))%(10**9+7)
print(suma)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*((2**i))%(10**9+7))%(10**9+7)
print(suma)
### BUGGY CODE ###

n = int(input())
cnt = 1
l = [2, 1]
while True:
    cnt += 1
    l.append(l[len(l)-1] + l[len(l)-2])
    if cnt == n:
        print(l[len(l) - 1])
        exit()


### FIXED CODE ###

n = int(input())
cnt = 1
l = [2, 1]
if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    while True:
        cnt += 1
        l.append(l[len(l)-1] + l[len(l)-2])
        if cnt == n:
            print(l[len(l) - 1])
            exit()
### BUGGY CODE ###

import sys


N, K = map(int, input().split())
h = list(map(int, input().split()))

sys.setrecursionlimit(N+2)
dp = [float('inf')] * N
dp[0] = 0


def rec(i):

    if dp[i] < float('inf'):
        return dp[i]

    res = float('inf')
    for j in range(1, K+1):
        if i >= j:
            res = min(res, rec(i - j) + abs(h[i] - h[i - j]))

    dp[i] = res
    return res


print(rec(N-1))

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf') for _ in range(N)]
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i - j >= 0:
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
print(dp[N-1])
### BUGGY CODE ###

import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = np.array([list(readline().decode('utf-8').rstrip()) for _ in range(H)])


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, visited, h, w, cnt):

    que = deque()
    for adj in adjacent_4(h, w):
        que.append([adj, cnt])

    while len(que) != 0:
        target, cnt_ = que.popleft()
        if (visited[target[0]][target[1]] !=
                -1) | (S[target[0]][target[1]] == '#'):
            continue
        visited[target[0]][target[1]] = cnt_
        for adj in adjacent_4(target[0], target[1]):
            que.append([adj, cnt_ + 1])


ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        visited = np.full(S.shape, -1)
        visited[h][w] = 0
        bfs(S, visited, h, w, 1)
        ans = max(ans, visited.max())

print(int(ans))


### FIXED CODE ###

import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = [list(readline().decode('utf-8').rstrip()) for _ in range(H)]


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, h, w):

    visited = [[10**9] * W for _ in range(H)]
    visited[h][w] = 1

    que = deque()
    que.append((h, w))

    while len(que) != 0:
        h_, w_ = que.popleft()
        acc = visited[h_][w_]

        for adj_h, adj_w in adjacent_4(h_, w_):
            if S[adj_h][adj_w] == '#':
                continue
            acc_ = acc + 1
            if acc_ >= visited[adj_h][adj_w]:
                continue
            visited[adj_h][adj_w] = acc_
            que.append((adj_h, adj_w))

    return max(visited[h][w] for h in range(H)
               for w in range(W) if visited[h][w] != 10**9) - 1


"""
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        ans = max(ans, bfs(S, h, w))
"""
ans = max(bfs(S, h, w) for h in range(H) for w in range(W) if S[h][w] != '#')
print(int(ans))
### BUGGY CODE ###

n = int(input())
key = []
value = []

for i in range(n):
    s = input()
    if s in key:
        value[key.index(s)] += 1
    else:
        key.append(s) 
        value.append(1)

m = max(value)
arr = []
y = len(key)

for j in range(y):
    if value[j] == m:
        arr.append(key[j])

arr.sort()
x = len(arr)
for k in range(x):
    print(arr[k])

### FIXED CODE ###

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

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

m = max(dic.values())
arr = []

for j in dic:
    if dic[j] == m:
        arr.append(j)

arr.sort()

for k in arr:
    print(k)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.buffer.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,1,S)]
heapify(dq)

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, v, w = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nv,nw))

for i in range(2,N+1):
    print(min(ans[i]))





### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#CD = [[0,0]] + [[10**9,10**9] for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

for i in range(2,N+1):
    print(min(ans[i]))
### BUGGY CODE ###

def main():
    S = input()
    N = len(S)
    ans = 0
    m = 2019
    div_list = [0]*2019
    div_list[0] += 1
    for i in range(N):
        num = int(S[i:])
        div_list[num%m] += 1


    for item in div_list:
        if item >= 2:
            ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
input = stdin.readline

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

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

A,B,N = map(int,input().split())
def floor(x):
  return int(x//1)
list = []
if N >= B:
  for x in range(B+1):
    list.append(floor((A*x)/B)-(A*floor(x/B)))
else:
  for x in range(N+1):
    list.append(floor((A*x)/B)-(A*floor(x/B)))
print(max(list))

### FIXED CODE ###

A,B,N = map(int,input().split())
def floor(x):
  return int(x//1)
list = []
if N >= B:
    list.append(floor((A*(B-1))/B)-(A*floor((B-1)/B)))
else:
    list.append(floor((A*N)/B)-(A*floor(N/B)))
print(max(list))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
point = 1
for i in range(k):
  point = point*a[i]
#print(point)
t = 0
for j in range(k, n):
  point0 = point
  point = point*a[j]/a[t]
  t+=1
  if point > point0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
#point = 1
t = 0
"""for i in range(t, n):
  point = point*a[i]"""
  
#print(point)
#t = 0
for j in range(k, n):
  #point0 = point
  #point = point*a[j]/a[t]
  if a[j] > a[t]:
    print("Yes")
  else:
    print("No")
  t+=1
### BUGGY CODE ###

N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())
    
    
def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = indexSort(L2)

Remain = [Ind[0]]
i = 0
while i < len(Ind)-1:
    now = Remain[-1]
    After = Ind[i+1:]

    skip = 0
    for after in After:
        if L2[now] > L1[after]:
#            print(L2[now], L1[after])
            skip += 1
        else:
#            print(after)
            Remain.append(after)
            break
    i += 1 + skip  
print(len(Remain))

### FIXED CODE ###

import numpy as np

N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())
    
    
def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = np.argsort(L2)

Remain = [Ind[0]]
i = 0
while i < len(Ind)-1:
    now = Remain[-1]
    After = Ind[i+1:]

    skip = 0
    for after in After:
        if L2[now] > L1[after]:
#            print(L2[now], L1[after])
            skip += 1
        else:
#            print(after)
            Remain.append(after)
            break
    i += 1 + skip  
print(len(Remain))
### BUGGY CODE ###

import queue
k = int(input())
q = queue.Queue([1,2,3,4,5,6,7,8,9])
c = 1
while True:
  x = q.get()
  if c == k:
    print(x)
    exit()
  if x%10 == 0:
    q.put(10*x)
    q.put(10*x+1)
  elif x%10 == 0:
    q.put(10*x+8)
    q.put(10*x+9)
  else:
    i = x%10
    q.put(10*x+i-1)
    q.put(10*x+i)
    q.put(10*x+i+1)
  c += 1
    
    
    


### FIXED CODE ###

k = int(input())
x = [1,2,3,4,5,6,7,8,9]
i = 0
xa = x.append
while len(x) < k:
  if x[i]%10 == 0:
    xa(10*x[i])
    xa(10*x[i]+1)
  elif x[i]%10 == 9:
    xa(10*x[i]+8)
    xa(10*x[i]+9)
  else:
    j = x[i]%10
    xa(10*x[i]+j-1)
    xa(10*x[i]+j)
    xa(10*x[i]+j+1)
  i += 1
print(x[k-1])
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n-N*n-N*h != 0:
            w = N*h*n/(4*h*n-N*n-N*h)
            if w == int(w) and w >= 1:
                print(h, n, int(w))
                exit()


### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n-N*n-N*h!=0:
            w = N*h*n/(4*h*n-N*n-N*h)
            if w == int(w) and w >= 1:
                print(h, n, int(w))
                exit()
### BUGGY CODE ###

from collections import *
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
r=0
f=Counter(a)
for i in a:
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      if(i//j==i and f[i]>1):
          ff=1
      if((j in f and j!=i) or (i//j  in f and j!=1)):
        ff=1
  if(ff==0):
    r+=1
print(r)
        
      


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 5
cnt = [0 for _ in range(M)]

for i in A:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    
    j = i
    while j < M:
        cnt[j] += 1
        j += i
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)