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

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

s = input()
if not ('ABC' in s):
  print(0)
  exit()

from collections import deque
S = deque(maxlen=200000)
for ss in s:
  S.append(ss)

ans = 0
ihavea = 0
ihaveab = 0
#保持してる文字列
tmpS = ''
while 1:
  try:
    tmp = S.popleft()
  except:
    print(ans)
    exit()
  if ihavea == 0 and ihaveab==0 and (tmp=='B' or tmp=='C'):
    continue
  if ihavea == 0 and ihaveab==0 and tmp=='A':
    ihavea = 1
    tmpS += 'A'
    continue
  if ihavea == 1 and tmp=='A':
    ihavea = 1
    tmpS += 'A'
    continue
  if ihavea == 1 and tmp=='C': #ノーチャン
    ihavea = 0
    tmpS = ''
    continue
  #AABとかになるパターンをまだ考慮してない
  if ihavea == 1 and tmp=='B':
    ihaveab = 1
    ihavea = 0
    tmpS += 'B'
    continue
  if ihaveab == 1 and tmp=='A': #惜しいけどabは無駄になる
    ihaveab = 0
    tmpS = ''
    S.appendleft('A')
    continue
  if ihaveab == 1 and tmp=='B':
    ihaveab = 0
    tmpS = ''
    continue
  if ihaveab == 1 and tmp=='C':
    ihaveab = 0
    ans += len(tmpS)-1
    for _ in range(len(tmpS)-1):
      S.appendleft('A')
    tmpS = ''
#    if tmpS == 'AB': tmpS = ''
#    else:
#      tmpS = tmpS[0:-2] #末尾のABを取り除くだけ
#      if tmpS[-1]=='A': ihavea = 1
#      elif tmpS[-2:]=='AB': ihaveab = 1
    continue





### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

s = input()
if not ('ABC' in s):
  print(0)
  exit()

from collections import deque
S = deque(maxlen=200000)
tmp = 'C'
for ss in s:
  if tmp == 'B' and ss == 'C':
    S.pop()
    S.append('D')
    tmp = 'C'
  elif ss == 'C':
    S.append('B')
    tmp = 'C'
  else:
    S.append(ss)
    tmp = ss

ans = 0
ihavea = 0
#保持してる文字列
Acnt = 0
while 1:
  try:
    tmp = S.popleft()
  except:
    print(ans)
    exit()
  if tmp=='B':
    ihavea = 0
    Acnt = 0
    continue
  if ihavea == 0 and tmp=='A':
    ihavea = 1
    Acnt += 1
    continue
  if ihavea == 1 and tmp=='A':
    ihavea = 1
    Acnt += 1
    continue
  if ihavea == 1 and tmp=='D':
    ihavea = 1
    ans += Acnt
    #Aはそのまま引き継ぐ
    continue
### BUGGY CODE ###

A, B, K = [int(_) for _ in input().split()]
for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
print(A, B)


### FIXED CODE ###

A, B, K = [int(_) for _ in input().split()]
if A >= K:
    print(A-K, B)
else:
    print(0, max(0, B-(K-A)))
### BUGGY CODE ###

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

ans_list = []
for i in range(N):
    ans_list.append(A_list.index(i + 1) + 1)

print(' '.join(map(str, ans_list)))

### FIXED CODE ###

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

ans_list = [0] * N

for index, i in enumerate(A_list):
    ans_list[i - 1] = index + 1

print(' '.join(map(str, ans_list)))
### BUGGY CODE ###

# 貪欲法 + 山登り法 + スワップ操作
import time
s__ = time.time()
limit = 1.9
#limit = 10

from numba import njit
import numpy as np

d = int(input())
cs = list(map(int, input().split()))
cs = np.array(cs, dtype=np.int64)
sm = [list(map(int, input().split())) for _ in range(d)]
sm = np.array(sm, dtype=np.int64)

@njit('i8(i8[:], i8)', cache=True)
def total_satisfaction(ts, d):
    ls = np.zeros(26, dtype=np.int64)
    s = 0
    for i in range(d):
        t = ts[i]
        t -= 1
        s += sm[i][t]
        ls[t] = i + 1

        dv = cs * ((i+1) - ls)
        s -= dv.sum()
    return s

@njit('i8(i8, i8[:], i8)', cache=True)
def loop(mxsc, ts, tmpr):
    it = 100
    rds = np.random.randint(0, 4, (it,))
    rdd = np.random.randint(1, d, (it,))
    rdq = np.random.randint(1, 26, (it,))
    rdx = np.random.randint(1, 12, (it,))
    for i in range(it):
        bk1 = 0
        bk2 = 0
        if rds[0] == 0:
            # trailing
            di = rdd[i]
            qi = rdq[i]

            bk1 = ts[di]
            ts[di] = qi
        else:
            # swap
            di = rdd[i]
            xi = rdx[i]
            if di + xi >= d:
                xi = di - xi
            else:
                xi = di + xi
            
            bk1 = ts[di]
            bk2 = ts[xi]
            ts[di] = bk2
            ts[xi] = bk1

        sc = total_satisfaction(ts, d)

        delta = sc - mxsc
        if delta > 0:
            #print('d>0', mxsc, '->', sc)
            mxsc = sc
        else:
            # Random < e^(Δ/T) の場合も更新
            exp = np.exp(delta / tmpr)
            #if i == 0:print('delta=', delta, 'tmpr=', tmpr, exp)
            r = np.random.random()
            if r <= exp:
                #print('d<0', mxsc, '->', sc, delta, tmpr, exp)
                mxsc = sc
            else:
                # 戻す
                if rds[0] == 0:
                    ts[di] = bk1
                else:
                    ts[di] = bk1
                    ts[xi] = bk2

    return mxsc

@njit('i8[:]()', cache=True)
def greedy():
    ts = np.array([0] * d, dtype=np.int64)
    for i in range(d):
        mx = -1e10
        mxt = None
        for t in range(1, 26+1):
            ts[i] = t
            s = total_satisfaction(ts, i + 1)
            if s > mx:
                mx = s
                mxt = t
        ts[i] = mxt
    return ts

ts = greedy()
#ts = np.random.randint(1, 26, (d,)).astype(np.int64)
mxsc = total_satisfaction(ts, d)
mxbk = mxsc

# annealing vars
t0 = 2e3
t1 = 6e2

s_ = time.time()
mxsc = loop(mxsc, ts, t0)
e_ = time.time()

consume = s_ - s__
elapsed = e_ - s_
#print('consume:', consume)
#print('elapsed:', elapsed)

if consume < limit:
    lp = int((limit - consume) / elapsed)
    for i in range(lp):
        t = i / lp
        tmpr = np.power(t0, 1 - t) * np.power(t1, t)
        mxsc = loop(mxsc, ts, tmpr)
        #print(mxsc)

for t in ts:    print(t)
#print(mxbk, mxsc)
#print(time.time() - s__)
#print(mxsc)


### FIXED CODE ###

d = int(input())
cs = list(map(int, input().split()))
sm = [list(map(int, input().split())) for _ in range(d)]

import random
for _ in range(d):
    t = random.choice(range(26)) + 1
    print(t)
### BUGGY CODE ###

import numpy as np
n, x, y = map(int, input().split())
dist = np.array([[i for i in range(n+1)] for _ in range(n+1)])

r = abs(x - y) - 1


for i in range(1, n+1):
    dist[i] = abs(dist[i] - i)
dist[x][y] = 1
dist[y][x] = 1
dist[x] = np.minimum(dist[x], dist[x][y] + dist[y])
dist[y] = np.minimum(dist[y], dist[y][x] + dist[x])

for i in range(n+1):
    dist[i] = np.minimum(dist[i], dist[i][y] + 1 + dist[x], dist[i][x] + 1 + dist[y])
    if i <= x:
        dist[i] = np.minimum(dist[i], dist[i][x] + 1 + dist[y])
    elif y <= i:
        dist[i] = np.minimum(dist[i], dist[i][y] + 1 + dist[x])
    else:
        dist[i] = np.minimum(dist[i],
                             dist[i][y] + 1 + dist[x]
                             )
        dist[i] = np.minimum(dist[i],
                             dist[i][x] + 1 + dist[y]
                             )



ans = np.zeros(n+1)
for row in dist[1:, 1:]:
    for j in row:
        if 0 <= j <= n-1:
            ans[j] += 1


for w in ans[1:n]:
    print(int(w//2))





### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0] * n
for i in range(1, n+1):
    for j in range(i, n+1):
        r = min(
            abs(i-j),
            abs(x-i) + 1 + abs(y-j),
            abs(y-i) + 1 + abs(x-j)
        )
        ans[r] += 1

print("\n".join(map(str, ans[1:])))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)
for i in range(1,N + 1):
    if (i) not in A: print(0)
    else: print(c[i])


### FIXED CODE ###

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

import sys
import time

def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1.7):
            print('-1')
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()


### FIXED CODE ###

import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()
### BUGGY CODE ###

import sys
from collections import defaultdict
def main():
    input = sys.stdin.readline
    n = int(input())
    nums_table = defaultdict(int)
    ans = 0
    for i in range(1, n+1):
        for j in range(i,n+1,i):
            nums_table[j-1] += 1
    for i, v in nums_table.items():
        ans += (i+1)*v
    print(ans)
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    nums_table = [2] * (n+1)
    ans = 0
    for i in range(1, n+1):
        nums_table[i] = 2
    nums_table[1] = 1
    for i in range(2, n//2+1):
        for j in range(2*i,n+1,i):
            nums_table[j] += 1
    for i in range(1, n+1):
        ans += i * nums_table[i]
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

point=1
for i in range(K):
    point*=A[i]

point_=point
for i in range(K,N):
    point_*=A[i]
    point_//=A[i-K]
    if point_>point:
        print('Yes')
    else:
        print('No')
    point=point_

### FIXED CODE ###

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

for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[0]]

  for _ in range(k):
    times += 1
    now = a[now] - 1
    roop = 0
    roop_start = 0

    if now in visit[0]:
      roop = times - visit[1][visit[0].index(now)] #何個の町でループしてるかをroopに代入
      roop_start = visit[1][visit[0].index(now)] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      break
    else:
      visit[0].append(now)
      visit[1].append(times)

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[-1 for _ in range(n)]]
  visit[1][0] = 0
  roop = 0
  roop_start = 0

  for _ in range(k):
    times += 1
    now = a[now] - 1

    if visit[1][now] != -1:
      roop_start = visit[1][now] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      roop = times - roop_start #何個の町でループしてるかをroopに代入
      break
    else:
      visit[0].append(now)
      visit[1][now] = len(visit[0]) - 1

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


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

N = int(input())


for n in range(1,N+1):
    if n < 3:
        print(0)
    else:
        M =int((n-2)**0.5)
        count = 0
        for x in range(1,M+1):
            #P=x**2+y**2+z**2+x*y+y*z+z*x
            for y in range(1,M+1):
                #Q=x**2+y**2+z**2+x*y+y*z+z*x
                for z in range(1,M+1):
                    #R = x**2+y**2+z**2+x*y+y*z+z*x
                    if x**2+y**2+z**2+x*y+y*z+z*x == n:
                        count = count + 1
                    else:
                        pass
        print(count)



### FIXED CODE ###

N = int(input())
lst = [0]*(N+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            p = (x+y)*(x+z)+y**2+z**2
            if p > N:
                break
            else:
                lst[p] += 1
for i in range(1,N+1):
    print(lst[i])
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,reverse=True,key=lambda x: x[1])
D = []

for B,C in BC:
    for b in range(B):
        D.append(C)

for i in range(len(D)):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break

print(sum(A))

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    N,M = map(int,input().split())
    A = sorted(list(map(int,input().split())))
    BC = [list(map(int,input().split())) for _ in range(M)]
    BC = sorted(BC,reverse=True,key=lambda x: x[1])
    D = []

    for B,C in BC:
        for b in range(B):
            if len(D) != N:
                D.append(C)
            else:
                break
        else:
            continue
        break

    for i in range(len(D)):
        if A[i] < D[i]:
            A[i] = D[i]
        else:
            break

    print(sum(A))

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

n =int(input())

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

result = -1

for i in range(n-1, -1, -2):
    if i != 0 and a.count(i) != 2 or i == 0 and a.count(i) != 1:
        result = 0
        break

if result == 0:print(result)
else:
    print(2**int(n/2) % (10**9 + 7))


### FIXED CODE ###

from  collections import Counter

n =int(input())

a = list(input().rstrip().split())

count_num = Counter(a)

result = True

if len(a) == n:
    if n % 2 == 0:
        for i in range(n-1, -1, -2):
            if count_num[str(i)] ==2:
                continue
            else:
                result = False
                break

    else:
        if count_num['0'] == 1:
            for i in range(n-1, 1, -2):                
                if count_num[str(i)] ==2:continue
                else:
                    result = False
                    break
        else:result=False

if result: print(2**int(n/2) % (10**9+7))
else:print(0)
### BUGGY CODE ###

def main():
    n,p=map(int,input().split())
    s=input()
    dp=[[-1,-1] for i in range(n)]
    for i in range(n):
        for j in range(i,n):
            if int(s[i:j+1])%p==0:
                dp[i]=[1,j+1]
                break

    ans=0
    for i in range(n):
        if dp[i]!=[-1,-1]:
            ans+=dp[i][0]
            if dp[i][1]!=n:
                if dp[dp[i][1]]!=[-1,-1]:
                    dp[dp[i][1]][0]+=dp[i][0]
    print(ans)

main()

### FIXED CODE ###

from itertools import groupby
n,p=map(int,input().split())
s=[int(i) for i in input()]
if p==2 or p==5:
    ans=0
    for i in range(n-1,-1,-1):
        #Rとなるもの
        if s[i]%p==0:
            ans+=(i+1)
    exit(print(ans))
S=[0]*(n+1)
po=[1]*(n+1)
for i in range(n):
    po[i+1]=po[i]*10
    po[i+1]%=p
for i in range(n-1,-1,-1):
    S[i]=S[i+1]+s[i]*po[n-1-i]
    S[i]%=p
t=[[S[i],i] for i in range(n+1)]
t.sort()
#[L,R)となるのの候補
u=[[i[1] for i in sorted(list(group))] for key,group in groupby(t,key=lambda x: x[0])]
ans=0
for v in u:
    ans+=(len(v))*(len(v)-1)//2
print(ans)
### BUGGY CODE ###


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


A_cs = [0]*(len(A)+1)
for i in range(1,len(A)+1):
    A_cs[i] = A_cs[i-1]+ A[i-1]

B_cs = [0]*(len(B)+1)
for i in range(1,len(B)+1):
    B_cs[i] = B_cs[i-1]+ B[i-1]

total = 0
for i in range(len(A_cs)):
    for j in range(len(B_cs)):
        if A_cs[i]+B_cs[j]<=K:
            if total < i+ j:
                total = i+ j

print(total)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = [0]+list(map(int, input().split()))
B = [0]+list(map(int, input().split()))
import itertools
A_cs = list(itertools.accumulate(A))
B_cs = list(itertools.accumulate(B))

total = 0
j = len(B)-1
for i in range(len(A_cs)):
    while (j >= 0):
        if A_cs[i] + B_cs[j] <= K:
                total = max(total,i + j)
                break
        j -= 1

print(total)
### BUGGY CODE ###

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

if d == 0:
    guess = n
else:

    guess = 2 * (n - d)
total = n ** m
print((guess*(n)**(m-2)*(m-1) / total))


### FIXED CODE ###

def solution():

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


    if d == 0:
        guess = n
        return (m-1)/n

    else:

        guess = 2 * (n - d)
        return (guess*(m-1)/n**2)

print(solution())
### BUGGY CODE ###

def main():
    N,K=map(int,open(0).read().split())
    keta=1
    flag=0
    A=K**keta
    while flag==0:
        if A<=N and A*K>N:
            print(keta+1)
            return
        A*=K
        keta= keta+1
main()

### FIXED CODE ###

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
    
def main():
    N,K=map(int,input().split())
    print(len(Base_10_to_n(N,K)))
main()
### BUGGY CODE ###

def divisors(n: int)->list:
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


def preparing_boxes(N: int, A: list)->list:
    B = []
    # C = [0] * N

    for i in range(N, 0, -1):
        # print('=== {} ==='.format(i))
        a = A[i-1]
        if a == 0:
            continue
        B.append(i)
        # C[i-1] = 1

        for div in divisors(i):
            # print(div)
            A[div-1] = 1 - A[div-1]

    # print(''.join(str(i) for i in C))

    return B


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = preparing_boxes(N, A)
    print(len(ans))
    print(' '.join(str(i) for i in ans))


### FIXED CODE ###

def divisors(n: int)->list:
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


def preparing_boxes(N: int, A: list)->list:
    B = []
    # C = [0] * N

    for i in range(N, 0, -1):
        # print('=== {} ==='.format(i))
        a = A[i-1]
        if a == 0:
            continue
        B.append(i)
        # C[i-1] = 1

        for div in divisors(i):
            # print(div)
            A[div-1] = 1 - A[div-1]

    # print(''.join(str(i) for i in C))

    return B


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = preparing_boxes(N, A)
    print(len(ans))
    print(' '.join(str(i) for i in ans))
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [[9]*(w+4)]
maze.append([9]*(w+4))
for i in range(h):
  s = input()
  tmp = [9,9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+4))
maze.append([9]*(w+4))
#print(maze)

pos = deque()
pos.append([ch+1,cw+1,0])
while len(pos)>0:
  x, y, hop = pos.popleft()
  #print(pos)
  #print[x,y,hop)
  if (x,y) == (dh+1,dw+1):
    print(hop)
    break
  maze[x][y] = 3
  
  if maze[x-1][y] <3:
    pos.appendleft([x-1,y,hop])
    maze[x-1][y] = 3  
    
  if maze[x+1][y] <3:
    pos.appendleft([x+1,y,hop])
    maze[x+1][y] = 3
    
  if maze[x][y-1] <3:
    pos.appendleft([x,y-1,hop])
    maze[x][y-1] = 3
    
  if maze[x][y+1] <3:
    pos.appendleft([x,y+1,hop])
    maze[x][y+1] = 3

  move =[(-2,0),(-2,1),(-2,2),(-2,-1),(-2,-2),(2,0),(2,1),(2,2),(2,-1),(2,-2),(0,-2),(-1,-2),(1,-2),(0,2),(-1,2),(1,2),(-1,1),(-1,-1),(1,1),(1,-1)]
  for dx,dy in move:
    if maze[x+dx][y+dy] <2:
      pos.append([x+dx,y+dy,hop+1])
      maze[x+dx][y+dy] = 2
  
else:
  print(-1)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [[9]*(w+4)]
maze.append([9]*(w+4))
for i in range(h):
  s = input()
  tmp = [9,9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+4))
maze.append([9]*(w+4))
#print(maze)

pos = deque()
pos.append([ch+1,cw+1,0])
while len(pos)>0:
  x, y, hop = pos.popleft()
  #print(pos)
  #print[x,y,hop)
  if (x,y) == (dh+1,dw+1):
    print(hop)
    break
  maze[x][y] = 3
  
  if maze[x-1][y] <3:
    pos.appendleft([x-1,y,hop])
    maze[x-1][y] = 3  
    
  if maze[x+1][y] <3:
    pos.appendleft([x+1,y,hop])
    maze[x+1][y] = 3
    
  if maze[x][y-1] <3:
    pos.appendleft([x,y-1,hop])
    maze[x][y-1] = 3
    
  if maze[x][y+1] <3:
    pos.appendleft([x,y+1,hop])
    maze[x][y+1] = 3

  move =[(-2,0),(-2,1),(-2,2),(-2,-1),(-2,-2),(2,0),(2,1),(2,2),(2,-1),(2,-2),(0,-2),(-1,-2),(1,-2),(0,2),(-1,2),(1,2),(-1,1),(-1,-1),(1,1),(1,-1)]
  for dx,dy in move:
    if maze[x+dx][y+dy] <2:
      pos.append([x+dx,y+dy,hop+1])
      maze[x+dx][y+dy] = 2
  
else:
  print(-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S =input()
for i in range(Q):
  l, r = map(int, input().split())
  print(S[l-1:r].count('AC'))
  

### FIXED CODE ###

N, Q = map(int, input().split())
S =input()
AC_list = [0]*N
count = 0
for i in range(1,N):
  if (S[i-1] + S[i]) == "AC":
    count +=1
  AC_list[i] = count

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