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

def prime_table(n):
    list = [True for _ in xrange(n + 1)]
    i = 2
    while i * i <= n:
        if list[i]:
            j = i + i
        while j <= n:
            list[j] = False
            j += i
        i += 1

    table = [i for i in xrange(n + 1) if list[i] and i >= 2]
    return table

table = prime_table(10000)
while True:
    try:
        n = int(raw_input())
    except EOFError:
        break
    
    l = (i for i in xrange(1,n+1))
    r = (i for i in xrange(n,0,-1))
    ans = 0
    for j,k in zip(l,r):
        if j in table and k in table:
            ans += 1
    print ans

### FIXED CODE ###

def prime_table_boolean(n):
    list1 = [True for _ in xrange(n + 1)]
    i = 2
    while i * i <= n:
        if list1[i]:
            j = i + i
        while j <= n:
            list1[j] = False
            j += i
        i += 1
    list1[1] = False
    del list1[0]

    #table = [i for i in xrange(n + 1) if list1[i] and i >= 2]
    #return table
    return list1

table = prime_table_boolean(10001)
while True:
    try:
        n = int(raw_input())
    except EOFError:
        break
    
    l = table[:n]
    r = l[::-1]
    ans = 0
    for j,k in zip(l,r):
        if j and k:
            ans += 1
    print ans
### BUGGY CODE ###

S=input()
T=input()
len0=len(S)
while len(S)<len(T)*2:
    S=S+S

S=S+S

p=26
mod=(1<<50)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

TABLE2=[0]# Rolling Hashのテーブル. 最初は0
LEN2=len(T)

for i in range(LEN2):
    TABLE2.append((p*TABLE2[-1]%mod+ord(T[i])-97)%mod)# テーブルを埋める

TH=TABLE2[-1]

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)

### FIXED CODE ###

S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)
### BUGGY CODE ###

n,m,s,t=map(int,input().split())
import numpy as np
import sys
def input(): return sys.stdin.readline().strip()
u,v,a,b=map(np.array,zip(*[map(int,input().split()) for i in range(m)]))
from scipy.sparse import csr_matrix
g1=csr_matrix((a,(u-1,v-1)),shape=(n,n))
g2=csr_matrix((b,(u-1,v-1)),shape=(n,n))
from scipy.sparse.csgraph import dijkstra
d1=dijkstra(g1,directed=False,indices=s-1)
d2=dijkstra(g2,directed=False,indices=t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')

### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[map(int,input().split()) for i in range(m)]
inf=10**20
c1=[[] for i in range(n)]
c2=[[] for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1].append((v-1,a))
    c1[v-1].append((u-1,a))
    c2[u-1].append((v-1,b))
    c2[v-1].append((u-1,b))
from heapq import heappop,heappush
def dij(c,N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v,w in c[u]:
            if w<inf:
                temp=d[u]+w
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d1=dij(c1,n,s-1)
d2=dij(c2,n,t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')
### BUGGY CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
N = int(input())
e = []
for _ in range(N):
  x, y = map(int, input().split())
  e.append((x, y))
t = pow(10, 6)
res = 0
for a in range(2):
  for b in range(2):
    xbias = (-1) ** a
    ybias = (-1) ** b
    for u in range(pow(10, 6) + 1):
      v = sqrt(t ** 2 - u ** 2) * ybias
      px = 0
      py = 0
      for i in range(N):
        x, y = e[i]
        if u * x * xbias + v * y * ybias > 0:
          px += x
          py += y
      res = max(res, sqrt(px ** 2 + py ** 2))
print(res)

### FIXED CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
N = int(input())
e = []
for _ in range(N):
  x, y = map(int, input().split())
  e.append((x, y))
res = 0
for i in range(N):
  for j in range(N):
    u = e[i][0] + e[j][0]
    v = e[i][1] + e[j][1]
    px = 0
    py = 0
    for k in range(N):
      x, y = e[k]
      if u * x + v * y > 0:
        px += x
        py += y
    res = max(res, sqrt(px ** 2 + py ** 2))
print(res)
### BUGGY CODE ###

N=int(input())
x=y=z=1

for i in range(1, N+1, 1):
    ans = [[x,y,z] for x in range(1,i+1,1) for y in range(1,i-x,1) for z in range(1,i-x-y,1) if x*x+y*y+z*z+x*y+y*z+z*x == i]
    print(len(ans))

### FIXED CODE ###

n = int(input())
 
ans = [0] * (n+1)
for x in range(1,110):
    for y in range(1,110):
        for z in range(1,110):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp <= n:
                ans[tmp] += 1
 
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(N+1)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i-1])

print(dp[N][N//2])



### FIXED CODE ###

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

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])
### BUGGY CODE ###

from collections import Counter

if __name__ == '__main__':
    MOD = 2019
    strS = input()
    S = [int(s) for s in strS]
    N = len(S)

    mods = []
    for idx, s in enumerate(S[::-1]):
        if idx == 0:
            mods.append(s % MOD)
        else:
            mods.append((mods[idx - 1] + s * 10 ** idx) % MOD)

    mods_cnt = Counter(mods)

    ans = 0
    for key, value in mods_cnt.items():
        if value >= 2:
            ans += value * (value - 1) // 2
        elif key == 0:
            ans += 1
    print(ans)


### FIXED CODE ###

from collections import defaultdict

if __name__ == '__main__':
    MOD = 2019
    strS = input()
    S = [int(s) for s in strS]
    N = len(S)

    mods = defaultdict(int)
    mods[0] += 1
    pow10_mod = 1
    prv_mod = 0
    for idx, s in enumerate(S[::-1]):
        tmp_mod = (prv_mod + s * pow10_mod) % MOD

        mods[tmp_mod] += 1
        pow10_mod = (pow10_mod * 10) % MOD
        prv_mod = tmp_mod

    ans = 0
    for key, value in mods.items():
        if value >= 2:
            ans += value * (value - 1) // 2

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

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=[]:
      que[i] = A[i-1].pop()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:
      que[que[i]] = 0      
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

### FIXED CODE ###

from collections import deque
import time

zuru = time.time()
N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)//2
    break
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    # A = [885, 8, 1, 128, 83, 32, 256, 206, 639, 16, 4, 128, 689, 32, 8, 64, 885, 969, 1]
    # N = len(A)

    n_satisfied = N
    for l in range(N):
        prev_sum_lr = A[l]
        prev_xor_lr = A[l]
        for r in range(l + 1, N):
            # print(A[l: r + 1])
            sum_lr = prev_sum_lr + A[r]
            xor_lr = prev_xor_lr ^ A[r]

            prev_sum_lr = sum_lr
            prev_xor_lr = xor_lr

            if sum_lr != xor_lr:
                break

            # print("OK: ", A[l: r + 1])
            n_satisfied += 1

    print(n_satisfied)


### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    # A = [885, 8, 1, 128, 83, 32, 256, 206, 639, 16, 4, 128, 689, 32, 8, 64, 885, 969, 1]
    # N = len(A)

    n_satisfied = 0
    sum_lr = 0
    xor_lr = 0
    l, length = 0, 0

    while True:
        while l + length != N and \
                sum_lr + A[l + length] == xor_lr ^ A[l + length]:
            sum_lr += A[l + length]
            xor_lr ^= A[l + length]
            length += 1

        # print("l, length", l, length)
        n_satisfied += length

        if l == N:
            break

        sum_lr -= A[l]
        xor_lr -= A[l]
        l += 1
        length -= 1

    print(n_satisfied)
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy
        if xx < 0 or xx >= H:
            continue

        if yy < 0 or yy >= W:
            continue

        if checked[xx][yy] == -1:
            checked[xx][yy] = checked[x][y] + 1
            queue.append((xx, yy))

# ans = 0
# for i in range(H):
#     for j in range(W):
#         if ans < checked[i][j]:
#             ans = checked[i][j]

print(np.max(checked))


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

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

#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
dp = [[ float('inf') for i in range(100001)] for _ in range(n)]


dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    for vb in range(100001):
        if dp[i-1][vb] != float('inf'):
            dp[i][vb] = dp[i-1][vb]
            tmp = min(dp[i][vb + L[i][1]], dp[i-1][vb] + L[i][0])
            if tmp <=W:
                dp[i][vb + L[i][1]] = tmp
                #print(vb + v, dp[i][vb+ v])
    dp[i][L[i][1]] = min(dp[i][L[i][1]], L[i][0])

ans =0
for v, w in enumerate(dp[n-1]):
    if w <=W and ans <=v:
        ans = v
print(ans)

### FIXED CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
### BUGGY CODE ###

N = int(input())

s = []
for i in range(N):
    s.append(sorted(input()))

result = 0
for i, elm in enumerate(s):
    for j in range(i+1, N):
        if s[j] == elm:
            result += 1

print(result)


### FIXED CODE ###

N = int(input())

s = ["".join(sorted(input())) for i in range(N)]

count = 0
d = {}
for elm in s:
    if elm in d:
        count += d[elm]
        d[elm] += 1
    else:
        d[elm] = 1

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

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

for y in range(N):
    price = 0
    a.pop(y)
    a.insert(0,0)
    hold_max = a[0]
    hold_min = a[0]
    for x in range(len(a)):
        if a[x] > 0 and a[x] > hold_max:
            price += a[x] - hold_max
            hold_min = 0
            hold_max = a[x]
        elif a[x] < 0 and a[x] < hold_min:
            price += abs(a[x]) - abs(hold_min)
            hold_max = 0
            hold_min = a[x]
        else:
            continue
    print(price*2)
    a = list(A)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.insert(0,0)
A.append(0)
price = 0
for x in range(n+1):
    price += abs(A[x+1]-A[x])
for x in range(1, n+1):
    s = price
    s = s + abs(A[x-1]-A[x+1]) - (abs(A[x-1]-A[x])+abs(A[x]-A[x+1]))
    print(s)
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
A = []
for i in range(1,N-K+1):
    A.append((min(P[i:i+K-1]),max(P[i:i+K-1])))
B = {}
cur = 0
for i in range(1,N):
    if P[i]<P[i-1]:
        if i-cur>=K:
            B[cur] = i-cur
        cur = i
if N-cur>=K:
    B[cur] = N-cur
d = 0
if len(B)>1:
    d = len(B)-1
cnt = 1
for i in range(K,N):
    if P[i]<A[i-K][1] or P[i-K]>A[i-K][0]:
        cnt += 1
print(cnt-d)

### FIXED CODE ###

from collections import deque
from bisect import bisect_right
N,K = map(int,input().split())
P = list(map(int,input().split()))
Lmax = []
Lmin = []
if P[1]>P[0]:
    flag = 1
else:
    flag = -1
for i in range(2,N):
    if P[i]>P[i-1]:
        if flag==1:continue
        else:
            Lmin.append([i-1,P[i-1]])
            flag = 1
    else:
        if flag==1:
            Lmax.append([i-1,P[i-1]])
            flag = -1
        else:continue
cnt = 0
flagMono = 0
indmin = bisect_right(Lmin,[K-1,P[K-1]])
Smax = deque([0])
Smin = deque([0])
for i in range(1,K):
    while Smax:
        if P[Smax[-1]]<P[i]:
            Smax.pop()
        else:break
    Smax.append(i)
    while Smin:
        if P[Smin[-1]]>P[i]:
            Smin.pop()
        else:break
    Smin.append(i)    
if P[0]==P[Smin[0]] and P[K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]==0):
    flagMono=1
    cnt += 1
elif P[0]==P[Smin[0]] and K<N and P[K]>P[Smax[0]]:
    pass
else:
    cnt += 1
for i in range(1,N-K+1):
    if Smax[0]==i-1:
        Smax.popleft()
    while Smax:
        if P[Smax[-1]]<P[i+K-1]:
            Smax.pop()
        else:break
    Smax.append(i+K-1)
    if Smin[0]==i-1:
        Smin.popleft()
    while Smin:
        if P[Smin[-1]]>P[i+K-1]:
            Smin.pop()
        else:break
    Smin.append(i+K-1)
    indmin = bisect_right(Lmin,[i+K-1,P[i+K-1]])
    if P[i]==P[Smin[0]] and P[i+K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]<=i):
        if flagMono==0:
            flagMono = 1
            cnt += 1
        else:
            pass
    elif P[i]==P[Smin[0]] and i+K<N and P[i+K]>P[Smax[0]]:
        continue
    else:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [[0]*20]
for i in a:
    tmp = []
    for j in range(20):
        tmp.append((i>>j&1)+s[-1][j])
    s.append(tmp)
l = 0
r = 0
ans = 0
while l < n:
    for j in range(20):
        if s[r+1][j]-s[l][j]>1:
            ans += r-l
            l += 1
            break
    else:
        if r < n-1:
            r += 1
        else:
            ans += n-l
            l += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [[0]*20]
for i in a:
    tmp = []
    for j in range(20):
        tmp.append((i>>j&1)+s[-1][j])
    s.append(tmp)
l = 0
r = 0
ans = 0
while l < n:
    for j in range(20):
        if s[r+1][j]-s[l][j]>1:
            ans += r-l
            l += 1
            break
    else:
        if r < n-1:
            r += 1
        else:
            ans += n-l
            l += 1
print(ans)
### BUGGY CODE ###

#Modified from #6728952
from bisect import *
from heapq import *
 
md = 998244353
n = int(input())
hp = []
for _ in range(n):
    heappush(hp, list(map(int, input().split())))
cy = [[0] * 4 for _ in range(n)]
xy = []
ys = []

cnt=[0]*n

for i in range(n):
	cnt[i]=pow(2,i,md)

for i in range(n):
    x, y = heappop(hp)
    s = bisect(ys, y)
#    cy[i][3] = pow(2, s, md)
#    cy[i][2] = pow(2, i - s, md)
    cy[i][3] = cnt[s]
    cy[i][2] = cnt[i - s]
    ys.insert(s, y)
    xy.append([x, y])
ys = []
for i in range(n - 1, -1, -1):
    x, y = xy[i]
    s = bisect(ys, y)
#    cy[i][0] = pow(2, s, md)
#    cy[i][1] = pow(2, n - 1 - i - s, md)
    cy[i][0] = cnt[s]
    cy[i][1] = cnt[n - 1 - i - s]
    ys.insert(s, y)
#ans = pow(2, n - 1, md) * n % md
ans = cnt[n - 1]* n % md
for i in range(n):
    c0, c1, c2, c3 = cy[i]
#    ans = (ans + (c0 - 1) * (c2 - 1) * c1 * c3 + (c1 - 1) * (c3 - 1) * c0 * c2
#           - (c0 - 1) * (c1 - 1) * (c2 - 1) * (c3 - 1)) % md
    ans = (ans + (c0 - 1) * (c2 - 1) * c1 * c3 + (c1 - 1) * (c3 - 1) * c0 * c2
           - (c0 - 1) * (c1 - 1) * (c2 - 1) * (c3 - 1)) % md
print(ans)


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    num3=0
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        len2=len(a2)
        def c1(num1):
            return a.count(num1)
        def l1():
            return len(a2)
        for i in range(len2):
            num=0
            if c1(a2[i-num3])==1:
                for j in range(i-num3):
                    if a2[i-num3]%a2[j]==0:
                        num=1
                        a2.remove(a2[i-num3])
                        num3+=1
                        break
                    if a2[i-num3]/2+1<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
num=a[-1]
dp=[True]*num
seen=[0]*num
for i in range(n):
    num2=a[i]
    if dp[num2-1]==True:
        if seen[num2-1]==1:
            dp[num2-1]=False
        for j in range(2,num//num2+1):
            dp[j*num2-1]=False
    seen[a[i]-1]=1
ans=0
for i in range(n):
    if dp[a[i]-1]==True:
        ans+=1
print(ans)