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

N = int(input())
X = input()

def e(x, y):
    if y <= 0: return -1
    res = 0
    z = 1
    for i in range(len(x) - 1, -1, -1):
        if x[i] == '1':
            res = (res + z) % y
        z = (z << 1) % y
    return res

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

fm = [-1] * (2 * (10 ** 5) + 1)
fm[0] = 0
def f(x):
    if fm[x] >= 0: return fm[x]
    fm[x] = 1 + f(x % popcount(x))
    return fm[x]


pc = X.count('1')
s0 = e(X, pc + 1)
s1 = e(X, pc - 1)

for i in range(N):
    t = 0
    if X[i] == '0':
        t = (s0 + e('1' + '0' * (N - i - 1), pc + 1)) % (pc + 1)
    else:
        if pc == 1:
            print(0)
            continue
        t = (s1 - e('1' + '0' * (N - i - 1), pc - 1)) % (pc - 1)
    print(1 + f(t))


### FIXED CODE ###

N = int(input())
X = input()

def e(x, y):
    t = [0] * len(x)
    if y <= 0: return (-1, t)
    if y == 1: return (0, t)
    res = 0
    z = 1
    for i in range(len(x) - 1, -1, -1):
        t[i] = z
        if x[i] == '1':
            res = (res + z) % y
        z = (z << 1) % y
    return (res, t)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

fm = [-1] * (2 * (10 ** 5) + 1)
fm[0] = 0
def f(x):
    if fm[x] >= 0: return fm[x]
    fm[x] = 1 + f(x % popcount(x))
    return fm[x]


pc = X.count('1')
s0, t0 = e(X, pc + 1)
s1, t1 = e(X, pc - 1)

for i in range(N):
    t = 0
    if X[i] == '0':
        t = (s0 + t0[i]) % (pc + 1)
    else:
        if pc == 1:
            print(0)
            continue
        t = (s1 - t1[i]) % (pc - 1)
    print(1 + f(t))
### BUGGY CODE ###

N, K = map(int, input().split())
where_go = list(map(int, input().split()))
now = 0
count = 0

while count < K:
    now = where_go[now] - 1
    count += 1

print(now + 1)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split())) #どこに行くかのリスト
now = 0 #どこにいるか
LOG = {}
roop = 0
count = 0

while now not in LOG and count < K:
    LOG.setdefault(now, count)
    now = A[now] -  1
    count += 1

if count < K:
    roop = len(LOG) - LOG[now]
    K = (K - count) % roop
    count = 0
    while count < K:
        now = A[now] -  1
        count += 1

print(now+1) #行った場所を保存
### BUGGY CODE ###

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append((a, b))
  if b == n:
    e.append((a, b))
    
for a, b in s:
  for a2, b2 in e:
    if b == a2:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

### FIXED CODE ###

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == n:
    e.append(a)

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N, M = map(int, input().split())
a_b = sorted([list(map(int, input().split())) + [0] for _ in range(M)])
ans = 0
for i in range(M):
    k = M - i - 1
    if a_b[k][2]:
        continue
    a_b[k][2], c = 1, a_b[k][0]
    for j in range(k):
        if a_b[j][0] <= c < a_b[j][1]:
            a_b[j][2] = 1
    ans += 1
print(ans)

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    a_b = sorted([list(map(int, input().split())) for _ in range(M)])
    used = [0] * M
    ans = 0
    for i in range(M):
        k = M - i - 1
        if used[k]:
            continue
        used[k], c = 1, a_b[k][0]
        for j in range(k):
            if a_b[j][0] <= c < a_b[j][1]:
                used[j] = 1
        ans += 1
    print(ans)

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

num = 7
k = int(input())
count=1
# i=1
while(True):
    if(num%k==0):
        print(count)
        break
    if(count>k):
        print(-1)
        break
    num = num*10+7
    count+=1
    



### FIXED CODE ###

num = 7
k = int(input())
count=1
# i=1
while(True):
    if((num%k)==0):
        print(count)
        break
    if(count>k):
        print(-1)
        break
    num = (num*10+7)%k
    count+=1
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
for i in range(M):
  B,C = map(int, input().split())
  for j in range(B):
    D.append(C)

import bisect
from collections import deque

D = sorted(D,reverse=True)
A = sorted(A)
A.extend(D[:N])
A = sorted(A,reverse=True)

print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [[] for _ in range(M)]
for i in range(M):
  BC[i] = list(map(int, input().split()))

BC.sort(key=lambda x: x[1], reverse=True)

for i in BC:
  A.extend([i[1]]*i[0])
  if len(A) > 2*N:
    break
    
A = sorted(A,reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

from collections import defaultdict, deque
from itertools import combinations

N, M, Q = map(int, input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(Q)]

D = defaultdict(set)
for a, b, c, d in ABCD:
  D[b-1].add((a-1, c, d))

for j in range(N-1, 0, -1):
  for x, y in combinations(D[j], 2):
    if x[0] == y[0]:
      continue
    if x[0] > y[0]:
      x, y = y, x
    if x[1] > y[1]:
      D[y[0]].add((x[0], x[1] - y[1], 0))

for i, j in combinations(range(N), 2):
  D[j].add((i, 0, 0))

que = deque([([1], 0)])
ans = 0
ans_L = []
while que:
  L, score = que.popleft()
  if len(L) == N:
    if score > ans:
      ans = score
      ans_L = L
  else:
    for a, c, d in D[len(L)]:
      l = L[a] + c
      if l <= M:
        que.append((L + [l], score + sum(d for a, c, d in D[len(L)] if l - L[a] == c)))
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque
from itertools import combinations

N, M, Q = map(int, input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(Q)]

D = defaultdict(dict)
for a, b, c, d in ABCD:
  D[b-1][(a-1, c)] = d

for j in range(N-1, 0, -1):
  for x, y in combinations(D[j], 2):
    if x[0] == y[0]:
      continue
    if x[0] > y[0]:
      x, y = y, x
    if x[1] > y[1]:
      if (x[0], x[1] - y[1]) not in D[y[0]]:
        D[y[0]][(x[0], x[1] - y[1])] = 0

for j in range(1, N):
  if (j-1, 0) not in D[j]:
    D[j][(j-1, 0)] = 0

que = deque([([1], 0)])
memo = set([(1,)])
ans = 0
while que:
  L, score = que.popleft()
  if len(L) == N:
    if score > ans:
      ans = score
  else:
    for a, c in D[len(L)]:
      l = L[a] + c
      if L[-1] <= l <= M:
        x = tuple(L + [l])
        if x not in memo:
          memo.add(x)
          que.append((L + [l], score + sum(d for v, d in D[len(L)].items() if l - L[v[0]] == v[1])))
print(ans)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  if s[ai]!=0:
    s[ai]=2
    continue
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)
### BUGGY CODE ###

T = input()
ans = ""
for i in T:
    if i == "?" or i == "D":
        ans += "D"
    else:
        ans += i
print(ans)

### FIXED CODE ###

T = input()
T = T.replace("?", "D")
print(T)
### BUGGY CODE ###

S = input()
K = int(input())

subList = set([])

for front in range(0, len(S)):
    for length in range(1, len(S) + 1):
        subList.add(S[front: front + length])

subList = list(subList)
subList.sort()

print(subList[K - 1])


### FIXED CODE ###

S = input()
K = int(input())

subList = set([])

for front in range(0, len(S)):
    for length in range(1, K + 1):
        subList.add(S[front: front + length])

subList = list(subList)
subList.sort()

print(subList[K - 1])
### BUGGY CODE ###

import itertools
import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, n + 1):
        # fact[i] = ((fact[i-1] * i) % p)
        # inv[i] = ((-inv[p % i] * (p // i)) % p)
        # factinv[i] = ((factinv[i-1] * inv[i]) % p)
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)


    return fact[n] * factinv[r] * factinv[n-r] % p


ans = 0
for i in range(N):
    num = combMod(i, K-1, mod) % mod
    ans += num * A[i] % mod
    ans -= num * A[N-i-1] % mod

print(ans%mod)

### FIXED CODE ###

# import itertools
# import math

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

mod = 10**9+7

# print(list(itertools.combinations(range(6), 3)))
# A = range(6)
# N = 6
# K = 3

# 二項係数を素数で割った余り
def combMod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
    # fact = [-1 for _ in range(n+1)]
    # fact[0] = 1
    # fact[1] = 1
    # inv = [-1 for _ in range(n+1)]
    # inv[0] = 0
    # inv[1] = 1
    # factinv = [-1 for _ in range(n+1)]
    # factinv[0] = 1
    # factinv[1] = 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
    
for i in range(2, N + 1):
    # fact[i] = ((fact[i-1] * i) % p)
    # inv[i] = ((-inv[p % i] * (p // i)) % p)
    # factinv[i] = ((factinv[i-1] * inv[i]) % p)
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)




ans = 0
for i in range(N):
    num = combMod(i, K-1, mod) % mod
    ans += num * A[i] % mod
    ans -= num * A[N-i-1] % mod
    ans %= mod

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

n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in range(n):
    if i+1 in pre.keys():
        pre[i+1].sort()
for i in range(m):
    num = str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1))
    while len(num) < 12:
        num = '0' + num
    print(num)

### FIXED CODE ###

import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
city = {}
yton = {}
for i in range(m):
    p,y = map(int, sys.stdin.readline().rstrip("\n").split())
    if p not in city.keys():
        city[p] = []
        city[p].append(y)
        yton[y] = i
    else:
        city[p].append(y)
        yton[y] = i
ans = [None]*m
for p in city.keys():
    city[p].sort()
    for i,y in enumerate(city[p]):
        ans[yton[y]] = str(p*(10**6)+i+1).zfill(12)
print(*ans, sep = '\n')
### BUGGY CODE ###

N = int(input())
S = [int(x) for x in list(input())]
total = 0
flag = True
for a in range(1000):
  flag = True
  for x in range(N-2):
    if S[x] == a//100:
      for y in range(x+1,N-1):
        if S[y] == a//10%10:
          for z in range(y+1,N):
            if a == S[x]*100+S[y]*10+S[z]:
              flag = False
              total += 1
              break
        if not flag:
          break
    if not flag:
      break
print(total)

### FIXED CODE ###

N = int(input())
S = [int(x) for x in list(input())]
total = 0
for a in range(1000):
  tmp = [a//100,a//10%10,a%10]
  i = 0
  for x in range(N):
    if tmp[i] == S[x]:
      i+=1
    if i==3:
      total+=1
      break
print(total)
### BUGGY CODE ###

n,m,k=map(int,input().split())
l=list(map(int,input().split()))
ll=list(map(int,input().split()))

l_ans=[]
for i in range(m+1):
  l_ans.append([0]*(n+1))
ct=0

for i in range(m+1):
  we=i+n
  for j in range(n+1):
    if i==0 and j==0:
      l_ans[i][j]=0
    elif i==0:
      l_ans[i][j]=l_ans[i][j-1]+l[j-1]
    elif j==0:
      l_ans[i][j]=l_ans[i-1][j]+ll[i-1]
    else:
      l_ans[i][j]=l_ans[i][j-1]+l[j-1]
    
    if l_ans[i][0]>k:
      we=0
    elif l_ans[i][j]>k:
      we=i+j-1
      break
    elif l_ans[i][j]==k:
      we=i+j
      break
  
  #print(ct,we)

  if we>ct:
    ct=we
#print(l_ans)
print(ct)


### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import numpy as np
N,M = map(int, input().split())
works_array = np.array([tuple(map(int, input().split())) for k in range(N)])
reward = 0
for k in range(M+1):
    workable_indices = np.where(works_array[:,0] <= k)[0]
    if workable_indices.shape[0] == 0:
        continue
    else:
        max_index = np.argmax(works_array[workable_indices, 1])
        reward += works_array[workable_indices[max_index], 1]
        works_array = np.delete(works_array, workable_indices[max_index], axis=0)
print(reward)

### FIXED CODE ###

import heapq
N,M = map(int, input().split())
works = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a not in works:
        works[a] = [b]
    else:
        works[a].append(b)
rewards = []
reward_sum = 0
for k in range(M+1):
    if k in works:
        print()
        for j in works[k]:
            heapq.heappush(rewards, -j)
    if len(rewards) != 0:
        reward_sum -= heapq.heappop(rewards)
print(reward_sum)
### BUGGY CODE ###

# coding=utf-8


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

X_list2 = X_list[:]
X_list2.sort()

for element in X_list:
    if X_list2.index(element) < (N-1)/2:
        print(X_list2[N//2])
    else:
        print(X_list2[(N//2 -1)])


### FIXED CODE ###

# coding=utf-8


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

X_list2 = X_list[:]
X_list2.sort()
smaller = X_list2[N//2 -1]
larger = X_list2[N//2]

for element in X_list:
    if element <= smaller:
        print(larger)
    else:
        print(smaller)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

index = []
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        index.append(i)

for le, ri in lr:
    count = 0
    for a in index:
        if le-1 <= a and a + 1 <= ri - 1:
            count += 1
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]
t = [0]
count = 0
for i in range(1, n):
    if s[i-1] + s[i] == 'AC':
        count += 1
    t.append(count)
for le, ri in lr:
    print(t[ri-1] - t[le-1])
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())
ls = np.array(list(map(int,input().split())))
inf = float("inf")
dp = [inf] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
for i in range(2,n):
    st = max(0,i-k)
    dp[i] = np.min(dp[st:i]+abs(ls[i]-ls[st:i]))
print(int(dp[n-1]))

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

n, m, k = map(int, input().split())

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

block = [[] for _ in range(n + 1)]

for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

def dfs(graph, start):
    visited = set([start])
    stack = []
    for f in graph[start]:
        stack.append(f)
    can_reach = set()
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                can_reach.add(c)
                stack.append(c)
    return can_reach

ans = []
for i in range(1, n + 1):
    c = dfs(graph, i)
    t = c - set(graph[i]) - set(block[i])
    ans.append(len(t))
print(*ans)

### FIXED CODE ###

n, m, k = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

block = [[] for _ in range(n + 1)]

for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

def dfs(graph, start):
    visited = set([start])
    stack = []
    can_reach = set([start])
    for f in graph[start]:
        stack.append(f)
        can_reach.add(f)
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                can_reach.add(c)
                stack.append(c)
    return can_reach

labels = [None] * (n + 1)
for i in range(1, n + 1):
    if labels[i] is None:
        c = dfs(graph, i)
        for j in c:
            labels[j] = [i, len(c)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(*ans)
### BUGGY CODE ###

x = list(map(int,input().split()))
N = x[0]
X = x[1]
Y = x[2]

import numpy as np
ans = np.zeros(N)
for i in range(1,N+1):
    for j in range(i,N+1):
        k = min(abs(i-j),abs(X-i)+1+abs(j-Y),abs(Y-i)+1+abs(j-X))
        ans[k] += 1

for i in range(1,N):
    print(int(ans[i]))

### FIXED CODE ###

x = list(map(int,input().split()))
N = x[0]
X = x[1]
Y = x[2]

ans = [0] * N

for i in range(1,N+1):
    for j in range(i,N+1):
        k = min(abs(i-j),abs(X-i)+1+abs(j-Y),abs(Y-i)+1+abs(j-X))
        ans[k] += 1

[print(int(x)) for x in ans[1:]]
### BUGGY CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    s.sort()
    for i in range(n - 1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                ans += 1
            else:
                break
    print(ans)


def SortString(text):
    return "".join(sorted(list(text)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    sDictionary = {}
    for i in range(n):
        if sDictionary.get(s[i]):
            ans += sDictionary.get(s[i])
            sDictionary[s[i]] += 1
        else:
            sDictionary[s[i]] = 1
    print(ans)


def SortString(text):
    return "".join(sorted(list(text)))


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

import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = raw_input("")
    tmp_s = ''.join(sorted(tmp))
    if smap.get(tmp_s, None) != None:
        smap[tmp_s] += 1
    else:
        smap[tmp_s] = 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print count


### FIXED CODE ###

import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = ''.join(sorted(raw_input("")))
    if smap.get(tmp, None) == None:
        smap[tmp] = 1
    else:
        smap[tmp] += 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print count
### BUGGY CODE ###

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7
mul = 1
# n桁目の?は10^nを13で割った余り(mul)と掛け合わせて足される

for i in range(N):
    for k in range(10):
        if S[-i-1] != '?' and S[-i-1] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j + mul * k) % 13] += dp[i][j]
    mul = (mul * 10) % 13
    for j in range(13):
        dp[i+1][j] %= MOD

res = dp[N][5]
print(res)


### FIXED CODE ###

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7
mul = 1
# n桁目の?は10^nを13で割った余り(mul)と掛け合わせて足される

for i in range(N):
    for k in range(10):
        if S[-i-1] != '?' and S[-i-1] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j + mul * k) % 13] += dp[i][j]
    mul = (mul * 10) % 13
    for j in range(13):
        dp[i+1][j] %= MOD

res = dp[N][5]
print(res)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = list (int(input()) for hogehoge in range(q))
acount = []
for i in range(1,n+1):
         acount.append(a.count(i))
for j in range(n):
         if acount[j] >= (q-k+1):
                  print("Yes")
         else:
                  print("No")


### FIXED CODE ###

from collections import Counter
n,k,q = map(int,input().split())
a = list (int(input()) for hogehoge in range(q))
acount = Counter(a)
for i in range(1,n+1):
         if acount[i] >= (q-k+1):
                  print("Yes")
         else:
                  print("No")
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def loop(N,A):
    res = 0
    for i in range(N):
        now = A[i]
        for j in range(N):
            if j == i:
                continue
            if now % A[j] == 0:
                res -= 1
                break
        res += 1
    return res


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

    A = np.array(A)

    res = loop(N,A)

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()