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

def resolve():
    a, b = map(int, input().split())
    d = []
    for i in range(2, min(a, b) + 1):
        if any([i % di == 0 for di in d]):
            continue
        if a % i == 0 and b % i == 0 and all([i % di != 0 for di in d]):
            d.append(i)
    d.append(1)
    print(len(d))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    a, b = map(int, input().split())
    div_a = set(prime_factorize(a))
    div_b = set(prime_factorize(b))
    print(len(div_a & div_b) + 1)
    # print(div_a)
    # print(div_b)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

# E

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

import scipy.special
res = 0
for k in range(K+1):
    res += M * (M - 1) ** (N - 1 - k) * scipy.special.comb(N-1, k, exact=True)

print(res % 998244353)

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
p = 998244353
comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p
print(res)
### BUGGY CODE ###

N = int(input())
adj = [list(map(int, input().split())) for i in range(N)]

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v in range(numV):
            if v == v_now:
                continue
            if cost[v_now] + adj[v_now][v] < cost[v]:
                cost[v] = cost[v_now] + adj[v_now][v]
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + adj[v_now][v] == cost[v]:
                num[v] = max(num[v], num[v_now] + 1)

    return (cost, num)


dist = [[] for i in range(N)]
num = [[] for i in range(N)]
for i in range(N):
    (dist[i], num[i]) = Dijkstra(N, i)

ans = sum(sum(adj[i]) for i in range(N)) // 2
for i in range(N):
    for j in range(i + 1, N):

        if dist[i][j] < adj[i][j]:
            ans = -1
            break

        if num[i][j] > 1:
            if dist[i][j] == adj[i][j]:
                ans -= dist[i][j]

    if ans == -1:
        break

print(ans)


### FIXED CODE ###

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

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

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

if n == 1:
    print(p)
else:
    for i in range(1,1000001):
        if p % (i ** n) == 0:
            ans = i
    print(ans)

### FIXED CODE ###

import math

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

tmp = math.sqrt(p)

if n == 1:
    print(p)
elif n >=100:
    print(1)
else:
    for i in range(1,int(tmp)+1):
        if p % (i ** n) == 0:
            ans = i
    print(ans)
### BUGGY CODE ###

import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
k = int(input())
#n, k = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    ans = 0
    for i in range(1, k+1):
        for j in range(1, k+1):
            for l in range(1, k+1):
                ans += gcd(i, j, l)
    print(ans)

main()




    


### FIXED CODE ###

import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
k = int(input())
#n, k = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    ans = 0
    for i in range(1, k+1):
        for j in range(1, k+1):
            if gcd(i, j) == 1:
                ans += k
                continue
            for l in range(1, k+1):
                ans += gcd(i, j, l)
    print(ans)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=II()
	A=[II() for _ in range(n)]

	#print(A)

	now=0
	cnt=1
	while True:
		now=A[now]-1
		if now==1:
			ans=cnt
			break
		elif now==0:
			ans=-1
			break
		else:
			cnt+=1
	print(ans)




if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	A=[0]+[II() for _ in range(n)]

	a=1

	for i in range(n+3):
		if a==2:
			ans=i
			break
		a=A[a]
	else:
		ans=-1

	print(ans)









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

N = int(input())
LRs = [list(map(int,input().split())) for i in range(0,N)]

L,R = zip(*LRs)
Lp = max(L)
Rq = min(R)

A = [max(0, r-Lp+1) for r in R]
B = [max(Rq-l+1, 0) for l in L]
AB = sorted(zip(A,B))
A2,B2 = zip(*AB)

mlr = max(r-l for l,r in LRs) + 1
m1 = max(0, Rq - Lp + 1) + mlr
for i,a in enumerate(A2[:-1:]):
    mt = min(B2[:i+1:])
    ms = A2[i+1]
    m1 = max(m1, ms+mt)

print(m1)

### FIXED CODE ###

N = int(input())
LRs = [list(map(int,input().split())) for i in range(0,N)]

L,R = zip(*LRs)
Lp = max(L)
Rq = min(R)

A = [max(0, r-Lp+1) for r in R]
B = [max(Rq-l+1, 0) for l in L]
AB = sorted(zip(A,B))
A2,B2 = zip(*AB)

mlr = max(r-l for l,r in LRs) + 1
m = max(0, Rq - Lp + 1) + mlr
mt = B2[0]
for i,a in enumerate(A2[0:-1:]):
    mt = min(mt, B2[i])
    ms = A2[i+1]
    m = max(m, ms+mt)

print(m)
### BUGGY CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))
P=map(int, input().split())
Acnt = [0 for i in range(M)]
sym = 0

for A in P:
    sym = (sym + A) % M
    Acnt[sym] += 1

print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))



### FIXED CODE ###

from collections import defaultdict
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
dd=defaultdict(int)
for p in P:
    dd[p%M]+=1
ans=0
def dou(x):
    return (x*(x-1))//2
for s in dd.values():
    ans+=dou(s)
print(ans)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
r = N//R
g = N//G
b = N//B
ans = 0

for i in range(r+1):
  for j in range(g+1):
    tmp = N - R*i - G*j
    if tmp >= 0 and tmp%B == 0:
      ans += 1
      
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
ans=0
 
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        b=N-(R*i+G*j)
        if b==0 or  b%B==0: 
            ans+=1
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):

    bc = [c for b,c in zip(B, C) for b_ in range(b)]
    # print(A+bc)
    k = sorted(A+bc)[-N:]
    print(sum(k))
    return


# Generated by 1.1.6 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()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):

    # bc = [c for b,c in zip(B, C) for b_ in range(b)]
    # print(A+bc)
    # k = sorted(A+bc)[-N:]
    a = [(l, 1) for l in A]
    for x, y in zip(C, B):
        a.append((x,y))


    n = N
    ans = 0
    for x, y in sorted(a, reverse=True):
        if n >= y:
            n -= y
            ans += x*y
        else:
            ans += x*n
            break
    
    print(ans)

    # print(sum(k))
    return


# Generated by 1.1.6 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()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

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

import math
import sys
N=int(input())
a=sys.stdin.readline().split()
A=[int(b) for b in a]
numbers=[0]*(2*10**5)
for a in range(1,N+1):
    kosuu=A.count(a)
    if kosuu<=1:
        pass
    else:
        numbers.insert(a-1,kosuu)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
answers=[0]*(2*10**5)
for a in range(1,N+1):
    if numbers[a-1]>=2:
        b=combinations_count(numbers[a-1],2)
        answers[a-1]+=b
kotae=sum(answers)
for a in range(N):
    z=A[a]
    if answers[z-1]==0:
        print(0)
    else:
        answer=kotae-numbers[z-1]+1
        print(answer)
        

### FIXED CODE ###

import math
import sys
from collections import Counter
N=int(input())
a=sys.stdin.readline().split()
A=[int(b) for b in a]
numbers=[0]*N
count=Counter(A)
kotae=0
for a in range(N+1):
    b=count[a]
    kotae+=b*(b-1)//2
for a in A:
    print(kotae+1-count[a])
### BUGGY CODE ###

import math


nums = [int(e) for e in input().split()]

a = nums[0]
b = nums[1]
n = nums[2]

max_score = -1
score = -1

for x in range(1, n+1):
    score = math.floor(a*x/b) - a* math.floor(x/b)
    if max_score < score:
        max_score = score
        x += 1
    elif x > b:
        break

print(max_score)


### FIXED CODE ###

import math


nums = [int(e) for e in input().split()]

a = nums[0]
b = nums[1]
n = nums[2]

max_score = -1
score = -1

# for x in range(1, n+1):
#     score = math.floor(a*x/b) - a* math.floor(x/b)
#     if max_score < score:
#         max_score = score
#     elif x > b:
#         break

if b > n:
    max_score = math.floor(a*n/b)
else:
    max_score = math.floor(a*(b-1)/b)

print(max_score)
### BUGGY CODE ###

n = int(input())
p = input().split()
cnt = 0
for i in range(n):
 ng_flg = 0
 ii = i
 for j in range(ii+1):
  if int(p[j]) < int(p[ii]) :
   ng_flg=1
   break
 if ng_flg == 0:
  cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
p = input().split()
min = int(p[0])
cnt = 0
for i in range(n):
 if int(p[i]) <= min:
  cnt+=1
 if int(p[i])<min :
  min = int(p[i])
print(cnt)
### BUGGY CODE ###

dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            for dx, dy in zip(dx_list, dy_list):
                x, y = w+dx, h+dy
                if not m_list[y][x]:
                    m_list[y][x] = True
                    new_q_list.append([y, x])
        q_list = new_q_list
    return cnt


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = []
    tmp_list = [True for _ in range(w_len+2)]
    m_list.append(tmp_list)
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append(tmp_list)
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a:
                q_list.append([h+1, w+1])
    ans = bfs(h_len, w_len, q_list)
    print(ans)
	

### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
### BUGGY CODE ###

def solve(A,N,K):
    for k in range(K):
        C = [0 for _ in range(N+1)]
        #C[i]:i番目の電球を照らす電球の数
        for i in range(N):
            C[max(i-A[i],0)] += 1
            C[min(i+A[i]+1,N)] -= 1
        for i in range(1,N):
            C[i] += C[i-1]

        if C[0] == N or C[N-1] == N:
            for i in range(N):
                A[i] = N
            break
        else:
            for i in range(N):
                A[i] = C[i]
    return A

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

    ans = solve(A,N,K)

    print(" ".join(map(str,ans)))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def solve(A,N,K):
    for k in range(K):
        C = [0 for _ in range(N+1)]
        #C[i]:i番目の電球を照らす電球の数
        for i in range(N):
            C[max(i-A[i],0)] += 1
            C[min(i+A[i]+1,N)] -= 1
        for i in range(1,N):
            C[i] += C[i-1]

        if C[0] == N or C[N-1] == N:
            for i in range(N):
                A[i] = N
            break
        else:
            for i in range(N):
                A[i] = C[i]
    return A

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

    ans = solve(A,N,K)

    print(" ".join(map(str,ans)))

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)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

for i in range(H):
	for j in range(W):
		que = deque()
		if A[i][j] == '#':
			dist[i][j] = 0
			que.append([i, j])
			while len(que) > 0:
				loc = que.popleft()
				try:
					if loc[0] < H - 1 and A[loc[0] + 1][loc[1]] == "." and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0] + 1, loc[1]])
				except:
					pass
				try:
					if loc[0] > 0 and A[loc[0] - 1][loc[1]] == "." and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0] - 1, loc[1]])
				except:
					pass
				try:
					if loc[1] < W - 1 and A[loc[0]][loc[1] + 1] == "." and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0], loc[1] + 1])
				except:
					pass
				try:
					if loc[1] > 0 and A[loc[0]][loc[1] - 1] == "." and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0], loc[1] - 1])
				except:
					pass

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

print(num)

### FIXED CODE ###


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

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

now = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			now.append([i,j])
			dist[i][j] = 0


while len(now) > 0:
	loc = now.popleft()
	if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] - 1])

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])
print(num)
### BUGGY CODE ###

def func1(i,N,S):
  indexS = 0 #Sの見ている場所
  indexI = 0 #3桁の暗証番号の見ている場所(0~2)
  i2 = str(i).zfill(3) # 0埋めしたi
  while indexS < N:
    if indexI > 2:
      break #探索終了
    if i2[indexI] == S[indexS]:
      indexI +=1
    indexS +=1
  return 1 if indexI >2 else 0

def main():
  N = int(input())
  S = input()
  print(sum([func1(i,N,S) for i in range(1000)]))

if __name__ == '__main__':
  main()

### FIXED CODE ###

def func1(i,N,S):
  indexS = 0 #Sの見ている場所
  indexI = 0 #3桁の暗証番号の見ている場所(0~2)
  i2 = str(i).zfill(3) # 0埋めしたi
  
  while indexS < N:
    if indexI > 2:
      break #探索終了
    if i2[indexI] == S[indexS]:
      indexI +=1
    indexS +=1
  return 1 if indexI >2 else 0

def main():
  N = int(input())
  S = input()
  print(sum([func1(i,N,S) for i in range(1000)]))

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

N, C = map(int, input().split())

x_list = [0, ]
v_list = [0, ]
x_oa = [0, ]
x_2oa = [0, ]

tmp_v = 0

for i in range(N):
    x, v = map(int, input().split())

    tmp_v += v

    x_list.append(x)
    v_list.append(v)
    x_oa.append(tmp_v - x)
    x_2oa.append(tmp_v - 2 * x)

x_list.append(C)
v_list.append(0)
x_oa.append(None)
x_2oa.append(None)

tmp_v = 0
ans = 0
for i in reversed(range(1, N + 2)):

    x = x_list[i]
    v = v_list[i]
    tmp_v += v
    # print(x, v, i)

    tmp_oa = tmp_v - 2 * (C - x) + max(x_oa[:i])
    tmp_2oa = tmp_v - C + x + max(x_2oa[:i])
    ans = max(ans, tmp_oa, tmp_2oa)

print(ans)

### FIXED CODE ###

N, C = map(int, input().split())

x_list = [0, ]
v_list = [0, ]
x_oa = 0
x_2oa = 0
max_a = {0: 0}
max_2a = {0: 0}

tmp_v = 0

for i in range(N):
    x, v = map(int, input().split())

    tmp_v += v

    x_list.append(x)
    v_list.append(v)
    x_oa = max(tmp_v - x, x_oa)
    x_2oa = max(tmp_v - 2 * x, x_2oa)
    max_a[i + 1] = x_oa
    max_2a[i + 1] = x_2oa

x_list.append(C)
v_list.append(0)

tmp_v = 0
ans = 0
for i in reversed(range(1, N + 2)):

    x = x_list[i]
    v = v_list[i]
    tmp_v += v
    # print(x, v, i)

    tmp_oa = tmp_v - 2 * (C - x) + max_a[i - 1]
    tmp_2oa = tmp_v - C + x + max_2a[i - 1]
    ans = max(ans, tmp_oa, tmp_2oa)

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

S = input()
N = len(S)
MOD = 10 ** 9 + 7

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i, s in enumerate(S[1:], 1):
    if s == '?':
        A[i] = A[i - 1] * 3 + Qs
        AB[i] = AB[i - 1] * 3 + A[i - 1]
        ABC[i] = ABC[i - 1] * 3 + AB[i - 1]
        Qs *= 3
    elif s == 'A':
        A[i] = A[i - 1] + Qs
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'B':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1] + A[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'C':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1] + AB[i - 1]

ans = ABC[-1] % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

N = int(input())
memo = []
for i in range(N):
  A = int(input())
  if(A in memo):
    memo.remove(A)
  else:
    memo.append(A)
print(len(memo))

### FIXED CODE ###

N = int(input())
A = [input() for _ in range(N)]

memo = {}
for a in A:
  if(a not in memo):
    memo[a] = 0
  else:
    memo.pop(a)
print(len(memo))
### BUGGY CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)
    min_len=0
    while max_len>min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif abs(min_len-max_len)==1 and min_len>=0 and li[min_len]!=a and max_len<len(li) and li[max_len]!=a:
            break
        elif li[mid]<a:
            min_len=mid
        else:
            max_len=mid
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)-1
    min_len=0
    while max_len>=min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif li[mid]<a:
            min_len=mid+1
        else:
            max_len=mid-1
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort()
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N, Q=map(int, input().split())
S=input()
num=[0]*N

for i in range(N-1):
  if S[i:i+2]=='AC':
    num[i]=1
    
num=[0]+num+[0]
    
for i in range(Q):
  l, r=map(int, input().split())
  print(sum(num[l:r]))

### FIXED CODE ###

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

counter=[0]+counter
for i in range(Q):
  l, r=map(int, input().split())
  print(counter[r-1]-counter[l-1])
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
a = []
for i in range(q):
    a.append(list(map(int,input().split())))
for i in range(q):
    if 'AC' in s[a[i][0]-1:a[i][1]]:
        ans = s[a[i][0]-1:a[i][1]].count('AC')
        print(ans)
    else:
        print(0)
    

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ans = []
a = [0]*(10**5+1)
add = 0
check = False
for i in range(n):
    if check and s[i] == 'C':
        add +=1
    if s[i] == 'A':
        check = True
    else:
        check = False
    
    a[i] += add
for i in range(q):
    b,c = map(int,input().split())
    ans.append(a[c-1]-a[b-1])
for i in range(q):
    print(ans[i])