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

import collections
X = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(X))
cl = list(c.keys())
cl.append(1)
for insu in cl:
    for i in range(-1000000, 1000000):
        if i**5 - (i-insu)**5 == X:
            print(i, (i-insu))
            break


### FIXED CODE ###

import collections
X = int(input())

for i in range(1000):
    for j in range(-1000,1000):
        if i**5 - j**5 == X:
            print(i,j)
            exit()
### BUGGY CODE ###

from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=False
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque
import math

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

    A.sort(reverse=True)

    Amax=max(A)

    dp=[0]*Amax

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop()
        if a==tmp:
            continue
        if dp[a-1]==0:
            if len(A)>0:
                if A[len(A)-1]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=1
                m+=1
        tmp=a

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

import sys
input = sys.stdin.readline
import math
import numpy as np

n, m = map(int, input().split())
*a, = map(int, input().split()) 

a = np.array(a)
a = a // 2

import fractions
from functools import reduce

def getLCM(a, b):
    return a * b // fractions.gcd(a, b)

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
*a, = map(int, input().split()) 

a = [ai >> 1 for ai in a]

import fractions
from functools import reduce

def getLCM(a, b):
    return a * b // fractions.gcd(a, b)

def f(x):
    cnt = 0
    while x%2 == 0:
        x //= 2
        cnt += 1
    return cnt

cnt = f(a[0])
for i in range(1, len(a)):
    if cnt != f(a[i]):
        print(0)
        break
else:
    lcm = reduce(lambda x, y: getLCM(x, y), a)
    ans = (m-lcm) // (lcm*2) + 1 if m >= lcm else 0
    print(ans)
### BUGGY CODE ###


import itertools


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
ans = 0
for idx in range(len(li)-1):
    ans += li[idx] * sum(li[idx+1:])

print(ans % MOD_NUMBER)


### FIXED CODE ###


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
nizyo_list = [i**2 for i in li]
ans = (sum(li)**2-sum(nizyo_list))//2
print(ans % MOD_NUMBER)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n+1):
    print(a.index(i)+1)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = [0 for _ in range(n)]
for i, v in enumerate(a):
    ans[v-1] = i+1
for i in ans: print(i)
### BUGGY CODE ###

import numpy as np
from fractions import gcd

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))


def main():
    x = 1
    ans = 0
    for a in A:
        tmp = gcd(x, a)
        # ans += (i) * A[i] // tmp + A[i] * x //tmp  
        x = (x * a) // tmp
    
    b = 0
    for a in A:
        b += x // a
        
    print(b%MOD)
main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N, M, Q = map(int, readline().split())
A = np.array(list(itertools.combinations_with_replacement(range(1, M+1), N)))

n = len(A) 

score = np.zeros(n, np.int32)
m = np.array(read().split(), np.int32).reshape(Q, 4)

ans = 0
for com in A:
    tmp = 0
    for a, b, c, d in m: 
        if com[b-1]-com[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement


def getPoint(data, A, q):
    res = 0
    for i in range(q):
        a, b, c, d = data[i]
        if A[b]-A[a] == c:
            res += d
    return res

def main():
    n, m, q = map(int, readline().split())    
    data = []
    for _ in range(q):
        a, b, c, d = map(int, readline().split())
        a-=1
        b-=1
        data.append((a, b, c, d))
    p = [int(i) for i in range(1, m+1)]
    ans = 0
    for A in combinations_with_replacement(p, n):
        ans = max(getPoint(data, A, q), ans)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)


n,m=map(int,input().split())
links=[[] for i in range(n)]
dp=[0 for i in range(n)]
pre_muls=[None for i in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)

dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)

n,m=map(int,input().split())
links=[[] for _ in range(n)]
dp=[0 for _ in range(n)]
pre_muls=[None for _ in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)
dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
cnt=0
for i in range(N//R+1):
    for j in range((N-i*R)//G+1):
            if i*R + j*G +((N-i*R-j*G)//B)*B==N:
                cnt+=1
print(cnt)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
cnt=0
for i in range(N//R+1):
    for j in range((N-i*R)//G+1):
            if i*R + j*G +((N-i*R-j*G)//B)*B==N:
                cnt+=1
print(cnt)
### BUGGY CODE ###

import itertools
N=int(input())
L=list(map(int, input().split()))
S=0
L.sort()
C=list(itertools.combinations(L,3))
for i in range(len(C)):
    if C[i][0]+C[i][1]>C[i][2]:
        S+=1
print(S)

### FIXED CODE ###

import bisect

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

for i in range(N):
    for j in range(i+1,N):
        S+=bisect.bisect_left(L,L[i]+L[j])-j-1
print(S)
### BUGGY CODE ###

n=int(input())
s=input()
a=list(s.split())
ans=1
for i in range(0,n):
    ans=ans*int(a[i])
    if(ans>1000000000000000000):
        ans=-1
if(ans<0):
    print("-1")
else:
    print(ans)


### FIXED CODE ###

n=int(input())
s=input()
a=list(s.split())
ans=1
flag=0
for i in range(0,n):
    ans=ans*int(a[i])
    if(ans>1000000000000000000):
        ans=-1
        j=i
        flag=1
        break
f=0
if(flag==1):
    for i in range(j+1,n):
        if(int(a[i])==0):
            f=1
            ans=0
            break
if(ans<-1 and f==0):
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
from itertools import accumulate
import math
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒してない数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += b.sum(d[av])
    return ans


def solve(N: int, a: "List[int]"):

    left = 0
    right = max(a)+1
    while right - left > 1:
        mid = (right + left)//2
        # acc = [0]*N
        # for i in range(N):
        #     if a[i] >= mid:
        #         acc[i] = acc[i-1]+1
        #     else:
        #         acc[i] = acc[i-1]-1
        acc = (1 if aa >= mid else -1 for aa in a)
        acc = tuple(accumulate(acc))
        invs = inversion(acc)
        if invs < (N*(N+1)//4 + 1):
            right = mid
        else:
            left = mid
    print(left)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒していない組(l, r)の個数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += b.sum(d[av])
        b.add(d[av], 1)
    return ans


def solve(N: int, a: "List[int]"):

    def isOK(y):
        acc = (1 if aa >= y else -1 for aa in a)
        acc = tuple([0]) + tuple(accumulate(acc))
        invs = inversion(acc)
        if acc[0] == -1:
            invs -= 1
        return invs < (N*(N+1))//4

    def binary_search(x):

        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    ng, ok = binary_search(range(max(a)))
    print(ng)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

n = int(input())
gcd = [[0 for _ in range(200)] for _ in range(200)]
for i in range(200):
  for j in range(200):
    big = i+1
    sml = j+1
    while sml != 0:
      big,sml = sml,big%sml
    gcd[i][j] = big
#print(gcd)
ans = 0
for a in range(n):
  for b in range(n):
    for c in range(n):
      x = gcd[a][b]
      y = gcd[a][c]
      ans += gcd[x-1][y-1]
      #print(a,b,c,x,y,gcd[x][y])
print(ans)

### FIXED CODE ###

n = int(input())
gcd = [[0 for _ in range(200)] for _ in range(200)]
for i in range(200):
  for j in range(200):
    big = i+1
    sml = j+1
    while sml != 0:
      big,sml = sml,big%sml
    gcd[i][j] = big
#print(gcd)
ans = 0
for a in range(n):
  for b in range(n):
    for c in range(n):
      x = gcd[a][b]
      y = gcd[a][c]
      ans += gcd[x-1][y-1]
      #print(a,b,c,x,y,gcd[x][y])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

min_ind = 0
min_val = 3e9
for i in range(1, N):
    tmp = A[i]+A[i-1]
    if tmp < min_val:
        min_val = tmp
        min_ind = i

# ダムmin_indから決めていく
rain = [0 for i in range(N)]
start = min_ind
end = (start+N-1)%N
lim = min(A[end], A[start]) * 2
for r in range(lim, -1, -2):
    rain[start] = r
    now = (start+1)%N
    pre = start
    ok = False
    while now != start:
        rain[now] = (A[pre] - rain[pre] // 2) * 2
        if A[now] < rain[now]//2:
            break
        now = (now+1)%N
        pre = (pre+1)%N
    if now == start:
        if rain[now] == (A[pre] - rain[pre]//2) * 2:
            ok = True
    if ok:
        for i in range(N):
            print(rain[i], end="")
            if i != N-1:
                print(" ",end="")
            else:
                print()
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

x = [0] * N
S = sum(A)
x[0] = S - 2 * (sum(A[1:N:2]))
for i in range(1, N):
    x[i] = 2 * A[i-1] - x[i-1]

for i in range(N-1):
    print(x[i], end=" ")
print(x[N-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)):
    ans += A[i] * sum(A[0:i])
ans = ans % 1000000007
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
a_sum = 0
for i in range(len(A)):
    ans += A[i] * a_sum
    a_sum += A[i]
ans = ans % 1000000007
print(ans)
### BUGGY CODE ###

s= input();
q = int(input());
flag = 0;
while(q>0):
    q-=1;
    ls = list(map(str,input().split(" ")));
    if(ls[0]=='1'):
        flag +=1;
    else:
        if(flag%2 == 1):
            if(ls[1]=='2'):
                s=ls[2]+s;
            else:
                s=s+ls[2];
        else:
            
            if(ls[1]=='1'):
                s=ls[2]+s;
            else:
                s=s+ls[2];
if(flag%2==0):
    print(s);
else:
    print(s[::-1])

### FIXED CODE ###

s= input();
q = int(input());
flag = 0;
fornt = "";
back = "";
while(q>0):
    q-=1;
    ls = list(map(str,input().split(" ")));
    if(ls[0]=='1'):
        flag +=1;
    else:
        if(flag%2 == 1):
            if(ls[1]=='2'):
                fornt=ls[2]+fornt;
            else:
                back=back+ls[2];
        else:
            
            if(ls[1]=='1'):
                fornt=ls[2]+fornt;
            else:
                back=back+ls[2];
s = fornt+s+back
if(flag%2==0):
    print(s);
else:
    print(s[::-1])
### BUGGY CODE ###

N=int(input())
S=list(input())

def rgb(now,sec):
    if now=='R' and sec=='G':
        return 'B'
    if now == 'R' and sec == 'B':
        return 'G'
    if now == 'G' and sec == 'R':
        return 'B'
    if now == 'G' and sec == 'B':
        return 'R'
    if now == 'B' and sec == 'G':
        return 'R'
    if now == 'B' and sec == 'R':
        return 'G'

r=[0]*N+[0]
g=[0]*N+[0]
b=[0]*N+[0]

for i in reversed(range(N)):
    if S[i]=='R':
        r[i]=r[i+1]+1
        g[i]=g[i+1]
        b[i]=b[i+1]
    if S[i]=='G':
        r[i]=r[i+1]
        g[i]=g[i+1]+1
        b[i]=b[i+1]
    if S[i]=='B':
        r[i]=r[i+1]
        g[i]=g[i+1]
        b[i]=b[i+1]+1 
    
ans=0
for i in range(N-2):
    now = S[i]
    for j in range(i+1,N-1):
        if S[j] == now:
            continue
        else:
            sec = S[j]
            thi = rgb(now,sec)
            if thi=='R':
                ans += r[j+1]
            if thi=='G':
                ans += g[j+1]
            if thi=='B':
                ans += b[j+1]
            if j+(j-i) < N and S[j+(j-i)]==thi:
                ans-=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())

def rgb(now,sec):
    if now=='R' and sec=='G':
        return 'B'
    if now == 'R' and sec == 'B':
        return 'G'
    if now == 'G' and sec == 'R':
        return 'B'
    if now == 'G' and sec == 'B':
        return 'R'
    if now == 'B' and sec == 'G':
        return 'R'
    if now == 'B' and sec == 'R':
        return 'G'

r=[0]*N+[0]
g=[0]*N+[0]
b=[0]*N+[0]

for i in reversed(range(N)):
    if S[i]=='R':
        r[i]=r[i+1]+1
        g[i]=g[i+1]
        b[i]=b[i+1]
    if S[i]=='G':
        r[i]=r[i+1]
        g[i]=g[i+1]+1
        b[i]=b[i+1]
    if S[i]=='B':
        r[i]=r[i+1]
        g[i]=g[i+1]
        b[i]=b[i+1]+1 
    
ans=0
for i in range(N-2):
    now = S[i]
    for j in range(i+1,N-1):
        if S[j] == now:
            continue
        else:
            sec = S[j]
            thi = rgb(now,sec)
            if thi=='R':
                ans += r[j+1]
            if thi=='G':
                ans += g[j+1]
            if thi=='B':
                ans += b[j+1]
            if j+(j-i) < N and S[j+(j-i)]==thi:
                ans-=1
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc152/tasks/abc152_c
# -*- coding: utf-8 -*-
N = int(input())
P = input().split()
T = [1]*N
for i in range(len(P)):
  P[i] = int(P[i])
for i in  range(1,len(P)):
  for k in range(0,i):
    if P[i]>P[k]:
      T[i] = 0
print(T.count(1))

### FIXED CODE ###

#https://atcoder.jp/contests/abc152/tasks/abc152_c
# -*- coding: utf-8 -*-
N = int(input())
P = input().split()
T = []
L =0
T.insert(0,int(P[0]))
P[0] = int(P[0])
for i in  range(1,len(P)):
  P[i] = int(P[i])
  if T[-1]>=P[i]:
    L =+ 1
    if T[-1]>P[i]:
      T.append(P[i])
print(len(T))
### BUGGY CODE ###

N, M= (int(i) for i in input().split())

ans = set(range(1,N+1))

for i in range(M):
    L_tmp, R_tmp = map(int, input().split())
    ans = ans & set(range(L_tmp,R_tmp+1))

print(len(ans))


### FIXED CODE ###

N, M= (int(i) for i in input().split())

L_max = 1
R_min = N

for i in range(M):
    L, R = map(int, input().split())
    L_max = max(L_max,L)
    R_min = min(R_min,R)

ans = set(range(L_max,R_min+1))

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

n, m = map(int,input().split())
s = {}
for i in range(m):
    l, r = map(int,input().split())
    if i == 0:
        s = set(range(l,r+1))
    else:
        s = set(range(l, r+1)) & s
print(len(s))

### FIXED CODE ###

import heapq
n, m = map(int,input().split())
l = []
r = []
for i in range(m):
    line = list(map(int,input().split()))
    l.append(-line[0])
    r.append(line[1])
heapq.heapify(l)
heapq.heapify(r)
l_max = - heapq.heappop(l)
r_min = heapq.heappop(r)
if l_max > r_min:
    print(0)
else:
    print(r_min-l_max+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

rs = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    rs[l-1].append((i, r-1))

bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in rs[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)
### BUGGY CODE ###

import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    a = list_a.pop(0)
    list_a.append(a)
print(len(list_input) - anti_ans)


### FIXED CODE ###

import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()

# 倍数判断用のリストを作成
list_div = [0]*(max(list_input))

for i in list_input:
    # print(i)
    a = list_div[i-1]
    # list_div[i-1::i] = [1]*(len(list_div[i-1::i]))
    list_div[i-1::i] = map(lambda x: x+1, list_div[i-1::i])
    if a == 1:
        pass
    else:
        # list_div[i-1] = 0
        pass

ans = 0
for i in list_input:
    if list_div[i-1] == 1:
        ans += 1

print(ans)