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

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

def prime(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True

a,b = MAP()
ans = 0
for i in range(1,min(a,b)+1):
    if (a%i==0) and (b%i==0):
        if prime(i):
            ans+=1

print(ans)

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

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

a,b = MAP()
print(len(set(prime_factorize(a)) & set(prime_factorize(b)))+1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD
    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        for wa in range(S+1):
            DP[i][wa] = 2*DP[i-1][wa]
            DP[i][wa] %= MOD
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    print(DP[N][S])
    return


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

N = int(input())

g = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    a = int(str(i)[0])
    b = int(str(i)[-1])
    g[a][b] += 1
ans = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        ans += g[i][j]*g[j][i]

print(ans)

### FIXED CODE ###

N = int(input())

g = [[0] * (10) for _ in range(10)]
for i in range(1, N + 1):
    a = int(str(i)[0])
    b = int(str(i)[-1])
    g[a][b] += 1
ans = 0
for i in range(1, 10):
    for j in range(1, 10):
        ans += g[i][j]*g[j][i]

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

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()  #从小到大
F.sort(reverse=True)  #从大到小

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
        if cost > k:
          return False
    return True

left = 0
right = A[-1] * F[0] + 1
while left < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid + 1
print(left)

### FIXED CODE ###

import numpy as np
i8 = np.int64
i4 = np.int32


def solve(A, F, K):
    min_ = 0
    max_ = 10 ** 12
    while min_ < max_:
        mid = (min_ + max_) // 2
        count = A - mid // F
        sum_ = count[count > 0].sum()
        if sum_ <= K:
            max_ = mid
        else:
            min_ = mid + 1
    return min_

def main():
    stdin = open('/dev/stdin', 'rb')
    pin = np.fromstring(stdin.read(), i8, sep=' ')
    N, K = pin[:2]
    A = pin[2: N + 2]
    F = pin[N + 2: 2 * N + 2]
    A = np.sort(A)[::-1]
    F.sort()
    ans = solve(A, F, K)
    print(ans)

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

from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



### FIXED CODE ###

from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))
### BUGGY CODE ###

import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

n = int(input())

gcd_num = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            g = math.gcd(i, j)
            gcd_num += math.gcd(g, k)
print(gcd_num)

### FIXED CODE ###

import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

n = int(input())

gcd_num = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        g = math.gcd(i, j)
        for k in range(1, n+1):
            gcd_num += math.gcd(g, k)
print(gcd_num)
### BUGGY CODE ###

n=int(input())
a=(input().split())
for i in range(n):
    x=0
    for j in range(n):
        for k in range(n):
            if j==i:
                continue
            elif k==i or j==k:
                continue        
            elif j>k and a[j]==a[k] and j!=i and k!=i:
                x=x+1
    print(x)


### FIXED CODE ###

def main():
    from collections import Counter
    n=int(input())
    a=list(map(int,input().split()))

    ctr = Counter(a)
    frm_n = sum(x * (x - 1) // 2 for x in ctr.values())

    ans = []
    for x in a:
        ans.append(frm_n - ctr[x] + 1)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int, input().split())); a.sort()
b = list(map(int, input().split())); b.sort()
c = list(map(int, input().split())); c.sort()
ab = [0 for i in range(n)]
bc = [0 for i in range(n)]

for i in range(n):
  ab[i] = bisect.bisect_left(a, b[i])
for i in range(n):
  bc[i] = sum(ab[:bisect.bisect_left(b, c[i])])
  
print(sum(bc))

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split())); a.sort()
b = list(map(int, input().split())); b.sort()
c = list(map(int, input().split())); c.sort()
ab = [0 for i in range(n)]
ans = 0

for i in range(n):
  ab[i] = ab[i-1] + bisect.bisect_left(a, b[i])
for i in range(n):
  tmp = bisect.bisect_left(b, c[i])
  if tmp != 0:
  	ans += ab[tmp-1] 

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

H, W, M = map(int, input().split())

targets = []
n_target_h = [0] * H
n_target_w = [0] * W

h_max = 0
w_max = 0
for i in range(M):
    h, w = map(int, input().split())
    targets.append((h, w))
    n_target_h[h - 1] += 1
    n_target_w[w - 1] += 1
    h_max = max(h_max, n_target_h[h - 1])
    w_max = max(w_max, n_target_w[w - 1])

bomb_h = [i + 1 for i, h in enumerate(n_target_h) if h == h_max]
bomb_w = [i + 1 for i, w in enumerate(n_target_w) if w == w_max]

ans = h_max + w_max - 1
for h in bomb_h:
    for w in bomb_w:
        if not (h, w) in targets:
            ans = h_max + w_max
            break
    else:
        continue
    break

print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())

targets = []
n_target_h = [0] * H
n_target_w = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    targets.append((h, w))
    n_target_h[h - 1] += 1
    n_target_w[w - 1] += 1

h_max = max(n_target_h)
w_max = max(n_target_w)

bomb_h = [i + 1 for i, h in enumerate(n_target_h) if h == h_max]
bomb_w = [i + 1 for i, w in enumerate(n_target_w) if w == w_max]

count = len(bomb_h) * len(bomb_w)
for target in targets:
    if (n_target_h[target[0] - 1] == h_max) and (n_target_w[target[1] - 1] == w_max):
        count -= 1

if count > 0:
    ans = h_max + w_max
else:
    ans = h_max + w_max - 1

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

n = int(input())
a = [int(input()) for _ in range(n)]

for _ in range(n):
    tmp = a.pop(0)
    print(max(a))
    a.append(tmp)


### FIXED CODE ###

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

n = int(input())
a = [int(input()) for _ in range(n)]
a_max_1 = max(a)
b = sorted(a, reverse=True)
a_max_2 = b[1]

for i in range(n):
    if a[i] == a_max_1:
        print(a_max_2)
    else:
        print(a_max_1)
### BUGGY CODE ###

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    r = 0
    for i in range(K + 1):
        r = (r + pow(25, i, mod) * pow(26, K - i, mod) * nCr(N + i - 1, N - 1)) % mod
    return r

        
print(main())


### FIXED CODE ###

def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    r = 0
    t = pow(26, K, mod)
    s = 1
    inv26 = pow(26, mod - 2, mod)
    inv = [0] * (K + 2)
    inv[1] = 1
    for i in range(2, K + 2):
        inv[i] = -inv[mod % i] * (mod // i) % mod
    for i in range(K + 1):
        r = (r + t * s) % mod
        t = (t * 25 * inv26) % mod
        s = (s * (N + i) * inv[i + 1]) % mod
    return r

        
print(main())
### BUGGY CODE ###

N = int(input())
S = input()
N_original = N

ans = 0
isleft = True

def f(n):
    for i in range(N_original - n+1):
        temp = S[i:i+n]
        if temp in S[i+n:]:
            return True
    return False

left = 0
right = N
N = N//4
while True:
    if f(N):
        if left == N:
            ans = left
            break
        left = N
    else:
        if right == N:
            ans = right
            break
        right = N
    N = (left + right)//2
print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
for i in range(m):
  if t[i] in d:
    d.remove(t[i])
  else:
    print("NO")
    exit()
print("YES")

### FIXED CODE ###

import collections

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
dc = collections.Counter(d)
tc = collections.Counter(t)
for i in tc:
    if tc[i] > dc[i]:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N = int(input())
S = [s for s in input()]
num = {s:[] for s in S}
for i, s in enumerate(S):
    num[s].append(i)
ans = 0
for i in range(1000):
    s = str(i).zfill(3)
    if s[0] in num.keys() and s[1] in num.keys() and s[2] in num.keys():
        for a in num[s[0]]:
            for b in num[s[1]]:
                for c in num[s[2]]:
                    if a < b < c:
                        ans += 1
                        break
                else:
                    continue
                break
            else:
                continue
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    c = 0
    idx_now = 0
    for j in range(3):
        idx = S[idx_now:].find(v[j])
        if idx == -1:
            break
        else:
            idx_now += idx + 1
            c += 1
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
pf={}
res = []
m= int(input())
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        res.append(i)
        m//=i
if m>1:
    res.append(m)
    pf[m]=1

cgg = deque()
for index in range(2**len(res)):

    s1 = 1
    s2 = 1
    for j in range(len(res)):
        if (index >> j & 1) == 1:
            s1 = s1 * res[j]
        else:
            s2 = s2 * res[j]

    cgg.append(s1-1 + s2 - 1)


print(min(cgg))




### FIXED CODE ###

import math

N = 10000000019
N = 50
N = 10
N = int(input())

result = []
for i in range(1, math.ceil(math.sqrt(N))+1):
    if N % i == 0:
        result.append((i + (N // i)) - 2)

print(min(result))
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
S=sum(A)

dp=[[0 for j in range(S+1)] for i in range(N)]
sub=[[0 for j in range(S+1)] for i in range(N)]
dp[0][0]=pow(2,N,mod)
dp[0][A[0]]=pow(2,N-1,mod)
sub[0][0]=1
sub[0][A[0]]=1

for i in range(1,N):
    for j in range(S+1):
        dp[i][j]=(dp[i-1][j]+pow(2,mod-2,mod)*(j>=A[i])*dp[i-1][j-A[i]])%mod
        sub[i][j]=(sub[i-1][j]+(j>=A[i])*sub[i-1][j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    ans+=3*sub[N-1][S//2]
    ans%=mod
    print(ans)


### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
inv=pow(2,mod-2,mod)
S=sum(A)

dp=[0 for j in range(S+1)]
sub=[0 for j in range(S+1)]
dp[0]=pow(2,N,mod)
dp[A[0]]=pow(2,N-1,mod)
sub[0]=1
sub[A[0]]=1

for i in range(1,N):
    for j in range(S,A[i]-1,-1):
        dp[j]=(dp[j]+inv*dp[j-A[i]])%mod
        sub[j]=(sub[j]+sub[j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    ans+=3*sub[S//2]
    ans%=mod
    print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
numbers = [x for x in range(1,N+1)]
a = 0
for i in numbers:
    for j in numbers:
        for k in numbers:
            if (i+j) % K == 0 and (i+k) % K == 0 and (k+j) % K == 0:
                a += 1
            else:
                pass
print(a)

### FIXED CODE ###

n,k = map(int,input().split())
num = (n // k) ** 3
if k % 2 == 0:
    if n - ((n // k) * k) < k // 2:
        print(num * 2)
    else:
        print(num + ((n // k + 1) ** 3))
else:
    print(num)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, w):
    w += leaves[x]
    for nx in [e for e in edge[x] if V[e] == 0]:
        V[nx] = 1
        dfs(nx, w)
    leaves[x] = w


N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
leaves = [0] * N
V = [0] * N

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    leaves[p] += x

V[0] = 1
dfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])


### FIXED CODE ###

from collections import deque


def bfs(x, w):
    q = deque()
    q.append((x, w))

    while len(q):
        x, w = q.popleft()
        leaves[x] += w
        w = leaves[x]
        for nx in edge[x]:
            if V[nx] == 0:
                V[nx] = 1
                q.append((nx, w))


N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
leaves = [0] * N
V = [0] * N

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    leaves[p] += x

V[0] = 1
bfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])
### BUGGY CODE ###

#300
N = int(input())
S = [input() for _ in range(N)]
L = []
L1 = []
S.sort()


for i in range(N):
    if i == 0:
        L.append(1)
        L1.append(S[i])
    else:
        if S[i-1] == S[i]:
            L[len(L)-1] = L[len(L)-1] + 1
        else:
            L.append(1)
            L1.append(S[i])

for i in range(len(L)):
    if L[i] == max(L):
        print(L1[i])

### FIXED CODE ###

#300
N = int(input())
S = [input() for _ in range(N)]
L = [0 for _ in range(N)]
L1 = ["" for _ in range(N)]
S.sort()
k = 0


for i in range(N):
    if i == 0:
        L[k] = 1 
        L1[k] = S[i]
    else:
        if S[i-1] == S[i]:
            L[k] = L[k] + 1
        else:
            L[k+1] = 1
            L1[k+1] = S[i]
            k += 1

m = max(L)
for i in range(N):
    if L[i] == m:
        print(L1[i])
### BUGGY CODE ###

from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node,max_val=0):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

max_val = bfs(0)
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])


### FIXED CODE ###

from collections import deque
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
# bfsによる色付けを行う
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])
### BUGGY CODE ###

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

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

# AC探索
loc = []
for i in range(N-1):
    if S[i:i+2] == "AC":
        loc.append(i)

# lrの各セットにlocに含まれる位置がいくつあるのか調べる
for l,r in lr:
    cn = 0
    for i in range(l-1,r-1):
        if i in loc: cn += 1
    print(cn)




### FIXED CODE ###

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

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