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

n,q=map(int,input().split())
s=list(input())

c=[0]
for i in range(n-1):
  if s[i]+s[i+1]=='AC':
    c.append(1)
  else:
    c.append(0)
  
cs=[sum(c[:i+1]) for i in range(n)]
#print(cs)
for _ in range(q):
  l,r=map(int,input().split())
  print(cs[r-1]-cs[l-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=list(input())

c=[0]
for i in range(n-1):
  if s[i]+s[i+1]=='AC':
    c.append(1)
  else:
    c.append(0)
  
cs=[c[0]]
for i in range(1,n):
  cs.append(cs[i-1]+c[i])
#print(cs)
for _ in range(q):
  l,r=map(int,input().split())
  print(cs[r-1]-cs[l-1])
### BUGGY CODE ###

N,M = map(int,input().split())
mod = 1000000007

dp = [0]*(N+1)
dp[0] = 1
A = []

for _ in range(M):
    k = int(input())
    A.append(k)

if 1 in A:
   dp[1] = 0
   if 2 in A:
       dp[2] = 0
else:
    dp[1] = 1
    
for i in range(2,N+1):
    if i not in A:
        dp[i] = (dp[i-1] + dp[i-2])%mod

print(dp[-1])

### FIXED CODE ###

N,M = map(int,input().split())
mod = 1000000007

dp = [0]*(N+1)
dp[0] = 1
A = []
for _ in range(M):
    k = int(input())
    A.append(k)
A = sorted(A,reverse = True)

if len(A)>0:
    a = A.pop()
else: a = -1
        
if a == 1:
    dp[1] = 0
    if len(A)>0:
        a = A.pop()
    if a == 2:
        dp[2] == 0
else:
    dp[1] = 1
    
for i in range(2,N+1):
    if i == a:
        if len(A)>0:
            a = A.pop()
        #continue
    else:
        if dp[i-1] != 0 and dp[i-2] != 0:
            dp[i] = (dp[i-1] + dp[i-2])%mod
        elif dp[i-1] != 0:
            dp[i] = dp[i-1]%mod
        elif dp[i-2] != 0:
            dp[i] = dp[i-2]%mod
        else:
            dp[i] = 0
        
print(dp[-1])
### BUGGY CODE ###

n=int(input())
table=list(map(int,input().split()))
for i in range(n):
    for j in range(n):
        if (table[i]==table[j]) and (i!=j) :
            print("NO")
            exit()
print("YES")


### FIXED CODE ###

n=int(input())
table=sorted(list(map(int,input().split())))
for i in range(n-1):
    if table[i]==table[i+1]:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

s = list(input().rstrip())
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]

print(dp[n][5] % (10**9 + 7))


### FIXED CODE ###

s = list(input().rstrip())
n = len(s)
m = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i + 1][j] %= m
print(dp[n][5])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
i=1
while i < N+1:
    print(len([j for j in A if j == i]))
    i += 1

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import string
import itertools


def solve(s: str, K: int):

    part_set = set()
    for c in string.ascii_lowercase:
        for i in range(len(s)):
            if c == s[i]:
                part_set |= set(itertools.accumulate(s[i:]))
        if len(part_set) >= K:
            print(sorted(part_set)[K-1])
            return
                


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import string
import itertools


def solve(s: str, K: int):

    part_set = set()
    for c in string.ascii_lowercase:
        for i in range(len(s)):
            if c == s[i]:
                part_set |= set(itertools.accumulate(s[i:min(i+K,len(s))]))
        if len(part_set) >= K:
            print(sorted(part_set)[K-1])
            return
                


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)

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

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[2])

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][2])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
long=[abs(sum(A[i+1:])-sum(A[:i+1])) for i in range(N)]
x=long.index(min(long))+1
pl=max(sum(A[:x]),sum(A[x:]))
mi=min(sum(A[:x]),sum(A[x:]))
while mi<pl:
  mi+=1
  ans+=1
  if mi==pl:
    break
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
p=q=sum(A)
for i in range(N):
  p-=2*A[i]
  q=min(abs(p),q)
print(q)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
h = []
heappush(h, (0, x1-1, y1-1))
dp[x1-1][y1-1] = 0
while h:
    dist_xy, y, x = heappop(h)
    if y == x2 - 1 and x == y2 - 1:
        print(dist_xy)
        quit()
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y + dy[i] * j, x + dx[i] * j
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist_xy + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist_xy + 1
                    heappush(h, (dist_xy + 1, ny, nx))

print(-1)


            
    


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                if dist + 1 > dp[ny][nx]:
                    break
            else:
                break
print(-1)
### BUGGY CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 i, j = len(x), len(y)

 dsp = [[0 for col in xrange(j+1)] for row in xrange(i+1)]
 for i in xrange(1,i+1):
  for j in xrange(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print dsp[i][j]

q = input()
for i in range(q):
 LCS()

### FIXED CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 a, b = len(x), len(y)
 dsp1 = [0 for i in xrange(b+1)]
 for i in xrange(a):
  dsp2 = dsp1+[]
  for j in xrange(b):
   if x[i] == y[j]:
    dsp1[j+1] = dsp2[j] + 1
   elif dsp1[j+1] < dsp1[j]:
    dsp1[j+1] = dsp1[j]
 print max(dsp1)
  
n = input()
for a in xrange(n):
    LCS()
### BUGGY CODE ###

N ,Q = map(int, input().split())
S = input()

pos = []
for i in range(Q):
    pos.append(list(map(int, input().split())))
    
def countAC(S, r, l):
    data = S[r-1:l]
    cnt = 0
    for i in range(len(data)-1):
        if data[i]=='A':
            if data[i+1] == 'C':
                cnt+=1
    return cnt
  
for it in pos:
    cnt = countAC(S, it[0], it[1])
    print(cnt)

### FIXED CODE ###

N ,Q = map(int, input().split())
S = input()

cumul = [0]*len(S)
cnt = 0
for i in range(len(S)-1):
    cumul[i] = cnt
    if S[i]=='A':
        if S[i+1] == 'C':
            cnt+=1
cumul[-1]=cnt

ret = []
for i in range(Q):
    l, r = map(int, input().split())
    cnt = cumul[r-1] - cumul[l-1]
    ret.append(str(cnt))
print('\n'.join(ret))
### BUGGY CODE ###

N, M = map(int, input().split())
AB_list = [tuple(map(int, input().split())) for i in range(N)]

# sorted_AB_list = sorted(AB_list, key=lambda x:x[0], reverse=False)
# sorted_AB_list = sorted(sorted_AB_list, key=lambda x:x[1], reverse=True)

sorted_AB_list = sorted(AB_list, key=lambda x:x[1], reverse=True)

money = 0

# 最終日から逆算
for i in range(M): # 残り日数
  remain_days = i+1
  
  for (A, B) in sorted_AB_list:
    if A <= remain_days:
      money += B
      sorted_AB_list.remove((A, B))
      break
  
print(money)
    
  

### FIXED CODE ###

from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        heappush(q, -jobs.pop(-1)[1])
    if q:
        ans -= heappop(q)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
 
def resolve():
    def dfs(num, p=-1):
        for i in to[num]:
            if p == i:
                continue
            ns[i] += ns[num]
            dfs(i, num)
 
    n, q = map(int, input().split())
 
    to = [[] for _ in range(n)]
 
    for _ in range(n-1):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
 
    ns = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        ns[p] += x
 
    dfs(0)
    print(*ns)
resolve()


### FIXED CODE ###

from heapq import heappush,heappop

def resolve():
    n, q = map(int, input().split())

    hen = []
    for _ in range(n-1):
        a,b = map(int, input().split())
        heappush(hen,(a,b))

    ns = [0 for _ in range(n+1)]
    for _ in range(q):
        p, x = map(int, input().split())
        ns[p] += x

    # 操作はまとめられる。頂点nに対してpの和
    # 親から累積させながら末端へ下ろしていく

    while len(hen) > 0:
        a, b = heappop(hen)
        ns[b] += ns[a]

    print(*ns[1:n+1])
resolve()
### BUGGY CODE ###

s = input()
k = int(input())
s_list = []
for i in range(len(s)):
    for j in range(i,len(s)+1):
        if not s[i:j] in s_list:
            s_list.append(s[i:j])
s_list.sort()
print(s_list[k])

### FIXED CODE ###

s = input()
k = int(input())
s_list = []
for i in range(len(s)):
    for j in range(i,i+6):
        if not s[i:j] in s_list:
            s_list.append(s[i:j])
s_list.sort()
print(s_list[k])
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()
c = []
import itertools
for _, g in itertools.groupby(s):
  c.append(len(list(g)))

c = c + [0]
ans = 1

if s[0] == "1":
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))
else:
  c = [0] + c
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))

print(ans)

### FIXED CODE ###

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

c = [0]
import itertools
for _, g in itertools.groupby(s):
  c.append(c[-1] + len(list(g)))
  
c = c[1:]
if s[0] == "1":
  c = [0] + c
else:
  c = [0,0] + c
if s[-1] == "0":
  c = c + [c[-1]]

ans = 0
for i in range(0,len(c), 2):
  end = min(i+2*k+1, len(c)-1)
  ans = max(ans, c[end]-c[i])

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

N, M, Q = map(int, input().split())

import numpy as np
matrix = np.array([[0 for _ in range(N+1)] for _ in range(N+1)], dtype=np.int16)

pairs = [[0 for _ in range(N+1)] for _ in range(N+1)]
for L, R in (map(int, input().split()) for _ in range(M)):
    pairs[L][R] += 1

for i in range(1, N+1):
    for j in range(i, N+1):
        w = pairs[i][j]
        if w > 0:
            matrix[:i+1,j:] += w

for p, q in (map(int, input().split()) for _ in range(Q)):
    print(matrix[p,q])


### FIXED CODE ###

N, M, Q = map(int, input().split())

class Cell:
    def __init__(self):
        self.value = 0
        self.L = 0
    def __repr__(self):
        return str((self.value, self.L))

pairs = [[Cell() for _ in range(N+1)] for _ in range(N+1)]
for L, R in (map(int, input().split()) for _ in range(M)):
    cell = pairs[L][R]
    cell.value += 1
    cell.L = cell.value

for i in range(N-1, 0, -1):
    for j in range(i+1, N+1):
        cell = pairs[i][j]
        cell.L += pairs[i][j-1].L
        cell.value = cell.L + pairs[i+1][j].value
for p, q in (map(int, input().split()) for _ in range(Q)):
    print(pairs[p][q].value)
### BUGGY CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = 0
yen = 0

sortkey = lambda val: val[0]
AB.sort(key=sortkey)

for i in range(N):
    for j in range(int(AB[i][1])):
        cnt += 1
        yen += AB[i][0]
        if cnt == M:
            print(yen)
            break


### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = 0
yen = 0

sortkey = lambda val: val[0]
AB.sort(key=sortkey)

for i in range(N):
    if M >= AB[i][1]:
        cnt += AB[i][1]
        yen += AB[i][0] * AB[i][1]
        M -= AB[i][1]
    elif M < AB[i][1]:
        cnt += M
        yen += AB[i][0] * M
        M = 0
    if M == 0:
        print(yen)
        break
### BUGGY CODE ###

n, q = map(int,input().split())
c = [0] * n
c = list(map(int,input().split()))
u = []
for i in range(q):
    l , r =  map(int,input().split())
    u.append(len(set(c[l-1:r])))


for i in range(q):
    print(u[i])

### FIXED CODE ###

def main(N,Q,C,LR,A):
    data = [0]*(N+1)
    def add(i,x):
        i+=1
        while i <= N:
            data[i]+= x
            i+=i&-i 
            #下桁から最初に1が出現するところまで拾う
            #111 -> 1 , 1100 -> 100 , 1010 -> 1
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc = CC('my_module')
  
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return njit(f)
  
    main=cc_export(main,(i8,i8,i8[:],i8[:,:],i8[:]))
    cc.compile()
    exit()
  
def input(): return sys.stdin.buffer.readline()
N,Q=map(int, input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
#print(C)
LR_ = [0] * (Q*2)
for i in range(Q):
    LR_[i*2],LR_[i*2+1] = input().split()
LR=np.array(LR_, dtype=np.int64).reshape(Q,2)
#print(LR)
A=np.argsort(LR[:,1])

from my_module import main
print(*main(N,Q,C,LR,A),sep='\n')
### BUGGY CODE ###

N = int(input())
lis = []
for n in range(N):
    com = input().split()
    if com[0] == "insert":
        lis.insert(0,int(com[1]))
    elif com[0] == "delete":
        try:
            lis.remove(int(com[1]))
        except:
            pass
    elif com[0] == "deleteFirst":
        del lis[0]
    else:
        lis.pop()
#    print(*lis)
print(*lis)
    
    



### FIXED CODE ###

from collections import deque
N = int(input())
de = deque()
for n in range(N):
    com = input().split()
    if com[0] == "insert":
        de.appendleft(com[1])
    elif com[0] == "delete":
        try:
            de.remove(com[1])
        except:
            pass
    elif com[0] == "deleteFirst":
        de.popleft()
    else:
        de.pop()
print(*de)
### BUGGY CODE ###

OK = 0
NG = 10**10

mid = (OK+NG) // 2

s = 0
for i in range(mid):
    s += i

A, P = map(int, input().split())

print((A*3+P)//2)

### FIXED CODE ###

A, P = map(int, input().split(" "))

print((A*3+P)//2)
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy

# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()

'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''

'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''

'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''

'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''

'''
.append(要素)
.extend(要素)
.insert(場所,要素)
del 配列名[場所]
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
'''
copy.copy(配列名)
'''
'''
sort()50
sorted(reverse=true)
'''
'''
2分探索
bisect.bisect_left(リスト, 要素)
'''
num = int(stdin.readline().rstrip())
yaku = []
for el in range(1, num + 1):
    if (num % el == 0):
        yaku.append(el)
res = []
if (int(len(yaku)) % 2 == 0):
    res.append(yaku[int(len(yaku) / 2 - 1)])
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[1]-1))
else:
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[0]-1))


### FIXED CODE ###

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy

# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()

'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''

'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''

'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''

'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''

'''
.append(要素)
.extend(要素)
.insert(場所,要素)
del 配列名[場所]
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
'''
copy.copy(配列名)
'''
'''
sort()50
sorted(reverse=true)
'''
'''
2分探索
bisect.bisect_left(リスト, 要素)
'''


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


num = int(stdin.readline().rstrip())
yaku = make_divisors(num)
yaku.sort()

res = []
if (int(len(yaku)) % 2 == 0):
    res.append(yaku[int(len(yaku) / 2 - 1)])
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[1]-1))
else:
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[0]-1))
### BUGGY CODE ###

# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))

l_ = [num - i - 1 for i, num in enumerate(l)]
# print(l_)

count_list = []
for j in range(min(l_), max(l_) + 1):
    count = sum([abs(i - j) for i in l_])
    count_list.append(count)

print(min(count_list))




### FIXED CODE ###

from statistics import median

# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))
l_ = [num - i - 1 for i, num in enumerate(l)]
l_ = sorted(l_)

b = median(l_)

print(int(sum([abs(i-b) for i in l_])))
### BUGGY CODE ###

n,t=map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))
ab_r=list(reversed(ab))

dp1=[[0 for j in range(t)] for i in range(n+1)]
dp2=[[0 for j in range(t)] for i in range(n+1)]

for i in range(n):
    for j in range(t-1):
        if ab[i][0] <= j:
            dp1[i+1][j] = max(dp1[i][j],dp1[i][j-ab[i][0]]+ab[i][1])
        else:
            dp1[i+1][j] = dp1[i][j]
            
for i in range(n):
    for j in range(t-1):
        if ab_r[i][0] <= j:
            dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ab_r[i][0]]+ab_r[i][1])
        else:
            dp2[i+1][j] = dp2[i][j]
            
m=0
for i in range(1,n+1):
    for j in range(t-1):
        m=max(m,dp1[i-1][j]+dp2[n-i][t-1-j]+ab[i-1][1])
print(m)


### FIXED CODE ###

n,t=map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))
ab_r=list(reversed(ab))

dp1=[[0 for j in range(t)] for i in range(n+1)]
dp2=[[0 for j in range(t)] for i in range(n+1)]

for i in range(n):
    for j in range(t-1):
        if ab[i][0] <= j:
            dp1[i+1][j] = max(dp1[i][j],dp1[i][j-ab[i][0]]+ab[i][1])
        else:
            dp1[i+1][j] = dp1[i][j]
            
        if ab_r[i][0] <= j:
            dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ab_r[i][0]]+ab_r[i][1])
        else:
            dp2[i+1][j] = dp2[i][j]
            
m=0
for i in range(1,n+1):
    for j in range(t-1):
        m=max(m,dp1[i-1][j]+dp2[n-i][t-1-j]+ab[i-1][1])
print(m)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0;p=l[-1]
if l[0]==1:
  print(1 if n==1 else int(l[1]!=1));exit()
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  for j in range(x,p+1,x):
  	g[j]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
  elif f and i==n-1:
    an+=1
print(an)

### FIXED CODE ###

n,a=int(input()),sorted(list(map(int,input().split())))
m,s=a[-1],[0]*(a[-1]+1)
for i in a:
  s[i]+=1
for i in set(a):
	if s[i]:
		for j in range(i*2,m+1,i):s[j]=0
print(s.count(1))