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

n=int(input())
o=99999
for a in range(0,n+1,59049):
    if n-a>=0:
        na=n-a
        for b in range(0,na+1,46656):
            if na-b>=0:
                nb=na-b
                for c in range(0,nb+1,7776):
                    if nb-c>=0:
                        nc=nb-c
                        for d in range(0,nc+1,6561):
                            if nc-d>=0:
                                nd=nc-d
                                for e in range(0,nd+1,1296):
                                    if nd-e>=0:
                                        ne=nd-e
                                        for f in range(0,ne+1,729):
                                            if ne-f>=0:
                                                nf=ne-f
                                                for g in range(0,nf+1,216):
                                                    if nf-g>=0:
                                                        ng=nf-g
                                                        for h in range(0,ng+1,81):
                                                            if ng-h>=0:
                                                                nh=ng-h
                                                                for i in range(0,nh+1,36):
                                                                    if nh-i>=0:
                                                                        ni=nh-i
                                                                        for j in range(0,ni+1,9):
                                                                            if ni-j>=0:
                                                                                nj=ni-j
                                                                                for k in range(0,nj+1,6):
                                                                                    if nj-k>=0:
                                                                                        nk=nj-k
                                                                                        for l in range(0,nk+1,1):
                                                                                            if nk-l==0:
                                                                                                m=((a/59049)+(b/46656)+(c/7776)+(d/6561)+(e/1296)+(f/729)+(g/216)+(h/81)+(i/36)+(j/9)+(k/6)+l)
                                                                                                o=min(o,m)
print(int(o))

### FIXED CODE ###

n=int(input())
def zzz(k,m):
    r=0
    while k:
        r=r+k%m
        k=k//m
    return r
a=99999
for i in range(n+1):
    a=min(a,zzz(i,6)+zzz(n-i,9))
print(a)
### BUGGY CODE ###

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

b = [0] * (m)
c = [0] * (m)

for i in range(m):
	b[i], c[i] = map(int, input().split())

d = []

for i in range(m):
	for j in range(b[i]):
		d.append(c[i])

a.extend(d)
a.sort(reverse=True)

print(sum(a[:n]))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(i)) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.append((b, c))
a = sorted(a, key=lambda x: x[1])
res = 0
idx = 0
while idx < n:
    b, c = a.pop()
    p = min(b, n-idx)
    res += p * c
    idx += p
print(res)
### BUGGY CODE ###

s = input().split()
K = int(s[0])
A = int(s[1])
B = int(s[2])

bis = 1
money = 0

if float(B/A) > 2:
  change = 1
else:
  change = 0

for i in range(K):
  if change == 1:
    if bis >= A and i+1 < K:
      bis = bis - A
      money += 1
      continue
    if money >= 1:
      bis += B
      money -= 1
      continue
 
  bis = bis+1
 
print(bis)

### FIXED CODE ###

s = input().split()
K = int(s[0])
A = int(s[1])
B = int(s[2])
 
bis = 1
 
if B-A >  2:
  change = 1
else:
  change = 0
 
if change == 0:
  bis = bis + K
else:
  i = A - 1
  bis  = A
  k = K - i
  bis += (k//2)*(B-A)
  bis += k %2
print(bis)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if r*R+g*G>N:
            continue
        if (N-r*R-g*G)%B==0:
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if r*R+g*G>N:
            continue
        if (N-r*R-g*G)%B==0:
            ans += 1

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

# coding: utf-8

n, k = map(int, input().split())
h_list = list(map(int, input().split()))


def cmin(a, b):
    if a<b:
        return a
    else:
        return b

ans = [float("inf")]*(n)

ans[0] = 0
ans[1] = abs(h_list[1]-h_list[0])

for i in range(n):
    for j in range(1,k+1):
        if i+j > n-1:
            break
        ans[i+j] = cmin(ans[i+j], ans[i]+abs(h_list[i+j]-h_list[i]))
        
# print(ans)
print(ans[-1])

### FIXED CODE ###

# coding: utf-8
import numpy as np

n, k = map(int, input().split())
h_list = np.array([int(x) for x in input().split()])

ans = np.zeros(n, dtype=int)

for i in range(1, n):
    start = max(i-k, 0)
    ans[i] = np.min(ans[start:i] + np.abs(h_list[start:i] - h_list[i]))
        
# print(ans)
print(ans[-1])
### BUGGY CODE ###

import itertools
import numpy as np

N, M, X = map(int, input().split())
c_list = []
for _ in range(N):
  c_list.append(list(map(int, input().split())))
  
cand = []
e_list = [i for i in range(N)]
for e in itertools.combinations_with_replacement(e_list, N):
  sum_list = np.zeros(M)
  sum_maney = 0
  for i in set(e):
    sum_list += np.array(c_list[i][1:])
    sum_maney += c_list[i][0]
  flag = True
  for m in range(M):
    if not sum_list[m] >= X:
      flag = False
  if flag:
    cand.append(sum_maney)
if cand == []:
  print(-1)
else:
  print(min(cand))

### FIXED CODE ###

import itertools
import numpy as np
 
N, M, X = map(int, input().split())
c_list = []
for _ in range(N):
  c_list.append(list(map(int, input().split())))
  
cand = []
e_list = [i for i in range(N)]
for n in range(1, N+1):
  for e in itertools.combinations(e_list, n):
    sum_list = np.zeros(M)
    sum_maney = 0
    for i in set(e):
      sum_list += np.array(c_list[i][1:])
      sum_maney += c_list[i][0]
    flag = True
    for m in range(M):
      if not sum_list[m] >= X:
        flag = False
    if flag:
      cand.append(sum_maney)
if cand == []:
  print(-1)
else:
  print(min(cand))
### BUGGY CODE ###

import numpy as np
def main():
    listA=[]
    while True:
        try:
            listA.append(list(map(int,input().split())))
        except:
            break;
    N = listA[0][0]
    A = listA[1]
    B = listA[2]

    if sum(A) < sum(B):
        print(-1)
        return
    C = []

    C = np.array(A) - np.array(B)
    C = C.tolist()
    change_list = [i for i in C if i < 0]
    change_count = len(change_list)
    if change_count == 0:
        print(0)
        return
    max_ = 0
    while True:
        change_count += 1
        max_ += max(C)
        if abs(sum(change_list)) < max_:
            break
        C[C.index(max(C))] = 0

    print(change_count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    if sum(A) < sum(B):
        return -1

    C = [a-b for a,b in zip(A,B)]
    plus = [x for x in C if x > 0]
    minus = [x for x in C if x < 0]
    change = sum(minus)
    count = 0
    if change == 0:
        return 0

    for i in sorted(plus,reverse=True):
        if change >= 0:
            break
        change += i
        count += 1
    return count + len(minus)

print(solve())
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    for j in range(i,N):
        if (i != j):
            ans += (A[i] * A[j])
            ans %= 1000000007
print(ans)

### FIXED CODE ###

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

ans = 0
sum_list = sum(A)
for i in range(N):
    ans += A[i] * (sum_list - A[i])
    ans %= 1000000007
    sum_list -= A[i]
print(ans)
### BUGGY CODE ###

import math as mt

MAXN = 10000001

# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]


# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        # marking smallest prime factor
        # for every number to be itself.
        spf[i] = i

        # separately marking spf for
    # every even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):

        # checking if i is prime
        if (spf[i] == i):

            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):

                # marking spf[j] if it is
                # not previously marked
                if (spf[j] == j):
                    spf[j] = i

                # A O(log n) function returning prime


# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
    ret = list()
    while (x != 1):
        ret.append(spf[x])
        x = x // spf[x]

    return ret
sieve()
n = int(input())
ans = 0
for i in range(1,n+1):
    p = getFactorization(i)
    st = set(p)
    cnt = 1
    for j in st:
        cnt *= (p.count(j)+1)
    ans += i*cnt
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    k = n//i
    m = k*(k+1)//2
    ans += m*i
print(ans)
### BUGGY CODE ###

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


def f(l):
    left = 0
    right = i + 1
    while left + 1 < right:
        x = (left + right) // 2
        if test(x):
            left = x
        else:
            right = x


ans = 1
for i in range(1, N):
    tmp = sorted(P[:i])
    if tmp[0] >= P[i]:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
v = P[0]
for i in P:
    if i <= v:
        ans += 1
        v = i
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

d = [0]*(max(a)+3)

for i in range(0,max(a)+1):
    c = a.count(i)
    d[i+1] += c
    d[i] += c
    d[i+2] += c

print(max(d))

### FIXED CODE ###

cnt=[0]*100002
input()
for x in map(int,input().split()):
    cnt[x]+=1
    cnt[x+1]+=1
    cnt[x+2]+=1
print(max(cnt))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

INF = float('inf')
d = [[INF for _ in range(W)] for _ in range(H)]
# for i in range(H):
#     for j in range(W):
#         if grid[i][j] == '#':
#             d[i][j] = 0


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0

    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and d[nx][ny] > d[x][y] + 1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1


for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            bfs(i, j)

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, d[i][j])

print(res)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)
### BUGGY CODE ###

n = int(input())

result_num = 0
words = [sorted(str(input()))]
count_num = [1]

for i in range(n-1):
  word = sorted(str(input()))
  exist = 0
  
  for j, word_ in enumerate(words):
    if word == word_:
      result_num += count_num[j]
      count_num[j] += 1
      exist += 1
      
  if exist == 0:
    words.append(word)
    count_num.append(1)
  
print(result_num)

### FIXED CODE ###

n = int(input())

result_num = 0
count_dict = {''.join(sorted(str(input()))): 1}

for i in range(n-1):
  word = ''.join(sorted(str(input())))

  if word in count_dict.keys():
    result_num += count_dict[word]
    count_dict[word] += 1
  else:
    count_dict[word] = 1

print(result_num)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
  b[i],c[i]=map(int,input().split())

s=sum(a)

for i in range(q):
  while b[i] in a:
    s+=c[i]-b[i]
    a.remove(b[i])
    a.append(c[i])
  print(s)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
  b[i],c[i]=map(int,input().split())

s=sum(a)

#このコードはO(10**10)になる可能性があり、重すぎる
"""
for i in range(q):
  while b[i] in a:
    s+=c[i]-b[i]
    a.remove(b[i])
    a.append(c[i])
  print(s)
"""

cnt_list=[0]*(10**5+1)
for i in range(n):
  cnt_list[a[i]]+=1

for i in range(q):
  s+=(c[i]-b[i])*cnt_list[b[i]]
  cnt_list[c[i]]+=cnt_list[b[i]]
  cnt_list[b[i]]=0
  print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [[n-1 for n in list(map(int, input().split()))] + [-1] for _ in range(N)]
A = [a[::-1] for a in A]

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 0
    rest = N * (N-1)

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        have_match = False
        # O(N)
        tmp = now.copy()
        for i in range(N):
            if now[now[i]] == i:
                tmp[i] = A[i].pop()
                rest -= 1
                have_match = True
        now = tmp
        if not have_match:
            return -1
        day += 1

print(main(N, A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [[n-1 for n in list(map(int, input().split()))] + [-1] for _ in range(N)]
A = [a[::-1] for a in A]

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 0
    rest = N * (N-1)
    candidate = set(range(N))

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        # O(N)
        have_match = False
        # tmp = now.copy()
        # for i in range(N):
        #     if now[now[i]] == i:
        #         tmp[i] = A[i].pop()
        #         rest -= 1
        #         have_match = True
        # now = tmp
        change = []
        next_candidate = set()
        for i in candidate:
            if now[now[i]] == i:
                j = A[i].pop()
                change.append((i, j))
                # あとで(a, b)でnow[a] = bに更新する
                next_candidate.add(i)
                if j != -1:
                    next_candidate.add(j)
                
                rest -= 1
                have_match = True

        if len(change) == 0:
            return -1
        for (a, b) in change:
            now[a] = b
            
        candidate = next_candidate
        
        day += 1

print(main(N, A))
### BUGGY CODE ###

import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = [ord(x) for x in input()] + [-1]
    ans = 0
    s = -1
    while s < N-1-ans*2:
        s += 1
        for e in range(s+ans+1,N-ans):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                ans = max(ans,k)
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    def input():
        return sys.stdin.readline()
    N = int(input())
    S = "_" + input()

    dp = [[0 for k in range(N+1)] for l in range(N+1)]

    for k in range(1,N):
        for l in range(k+1,N+1):
            if S[k] == S[l]:
                dp[k][l] = dp[k-1][l-1] + 1
    ans = 0
    for k in range(1,N):
        for l in range(k+1,N+1):
            if l-k >= dp[k][l]:
                ans = max(ans,dp[k][l])

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

#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

N, M = [ int(x) for x in input().split() ]

nm = []
for _i in range(M):
    nm.append([ int(x) for x in input().split() ])

ans = { x: 1 for x in range(1, N+1) }

for _nm in nm:
    nums = range(_nm[0], _nm[1] + 1)
    new_ans = {}
    for n in nums:
        if n in ans:
            new_ans[n] = 1
    ans = new_ans

print(len(ans.keys()))

### FIXED CODE ###

#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

N, M = [ int(x) for x in input().split() ]

nm = []
for _i in range(M):
    nm.append([ int(x) for x in input().split() ])

ans = [1,N]

for _nm in nm:
    if ans[0] < _nm[0]:
        ans[0] = _nm[0]
    if ans[1] > _nm[1]:
        ans[1] = _nm[1]

print(max(ans[1] - ans[0] + 1,0))
### BUGGY CODE ###

# ABC093B - Small and Large Integers
a, b, k = list(map(int, input().rstrip().split()))
lst = []
ans = []
for i in range(a, b + 1):
    lst.append(i)
if k >= b - a:
    for i in lst:
        print(i)
else:
    for i in range(k):
        ans.append(lst[i])
    for j in range(-1, -k - 1, -1):
        if lst[j] not in ans:
            ans.append(lst[j])
    ans = sorted(ans)
    for k in ans:
        print(k)

### FIXED CODE ###

# ABC093B - Small and Large Integers
a, b, k = list(map(int, input().rstrip().split()))
ans = []

if k >= b - a:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(k):
        ans.append(a + i)
    for j in range(k):
        if b - j not in ans:
            ans.append(b - j)
    ans = sorted(ans)
    for k in ans:
        print(k)
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.append((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

from fractions import gcd

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    g = 1
    for a in aa:
        g = a * g // gcd(a, g)
    ans = 0
    for a in aa:
        ans = (ans + g // a) % (10 ** 9 + 7)
    print(ans)


main()


### FIXED CODE ###

from fractions import gcd

def main():
    n = input()
    aa = list(map(int, raw_input().split()))
    g = 1
    for a in aa:
        g *= a // gcd(a, g)
    ans = 0
    MOD = 10 ** 9 + 7
    g %= MOD
    for a in aa:
        ans = (ans + g * pow(a, MOD - 2, MOD)) % MOD
    print(ans)


main()
### BUGGY CODE ###

import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = {}
H = {}
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    if not h in H:
        H[h] = 1
    else:
        H[h] += 1
    
    if not w in W:
        W[w] = 1
    else:
        W[w] += 1

    HW[h][w] = 1

answer = 0
HMAXES = []
WMAXES = []
HMAX = max(H.values())
WMAX = max(W.values())

for ki, vi in H.items():
    if vi == HMAX:
        HMAXES.append(ki)
for ki, vi in W.items():
    if vi == WMAX:
        WMAXES.append(ki)

answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

### FIXED CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)
### BUGGY CODE ###

import math

a,b = map(int,input().split())


ans = 1
sosuu = [2]
A = min(a,b)+1
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    if all(L % L2 != 0 for L2 in sosuu):  # すべての既存素数で割り切れなかったら素数
        sosuu.append(L)
        if a%L==0 and b%L==0:
            ans += 1

if a%2==0 and b%2==0:
    ans += 1
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())

if min(a,b) == 1:
    print(1)
    exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

A = factorization(a)
B = factorization(b)
ans = len(set(A) & set(B))
print(ans+1)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)
i = 0
'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

'''for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_list[i] = 1'''

for _ in range(q):
    lr = tuple(map(int, input().split()))
    print(s.count("AC", lr[0]-1, lr[1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)

'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1] = ac_list[i] + 1
    else:
        ac_list[i+1] = ac_list[i]
# print(ac_list)
for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])