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

import sys
import os

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=input()
    S=input()
    # print(S)

    sum=0
    for i in range(len(S)):
        # print(i)
        for j in range(i+1,len(S)):
            if S[i]!=S[j]:
                for k in range(j+1,len(S)):
                    if S[j]!=S[k] and S[k]!=S[i] and j-i!=k-j:
                        sum+=1
                        # print(S[i]+S[j]+S[k])
    print(sum)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(input())
    S=input()
    # print(S)
    R=S.count('R')
    G=S.count('G')
    B=S.count('B')

    sum=R*G*B
    # print(sum)
    for i in range(N-2):
        # print(i)
        for j in range(i+1,-(-(N+i)//2)):
            k=2*j-i
            # print("i:"+str(i)+" j:"+str(j)+" k:"+str(k))
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                sum-=1
                # print(S[i]+S[j]+S[k])


    print(sum)

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

# -*- coding: utf-8 -*-
s = input()
mods = [0]*2019
mods[0] += 1
for i in range(len(s)):
    value = int(s[i:])
    mods[value % 2019] += 1
print(sum([mod*(mod-1)//2 for mod in mods]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()
mods = [0]*2019
mods[0] += 1
# for i in range(len(s)):
#     value = int(s[i:])
#     mods[value % 2019] += 1
base = 1
value = 0
for c in map(int, reversed(s)):
    value += (c*base) % 2019
    base = (base * 10) % 2019
    # value = int(s[i:])
    mods[value % 2019] += 1
print(sum([mod*(mod-1)//2 for mod in mods]))
### BUGGY CODE ###

n = int(input())
x,y = 1,1
for i in range(n):
    t,a = map(int,input().split())
    k = 0
    if x * a != y * t:
        while True:
            if t*k >= x and a*k >= y:
                break
            else:
                k += 1
        x = t * k
        y = a * k
print(x+y)

### FIXED CODE ###

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return (x//y) + 1

n = int(input())
T,A = 1,1
for _ in range(n):
    t,a = map(int,input().split())
    x = max(ceil(T,t),ceil(A,a))
    if x == 0:
        x = 1
    T,A = t*x,a*x
print(T+A)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
K = 12900
dp = [[[0]*K for j in range(w)] for i in range(h)]
dp[0][0][abs(A[0][0]-B[0][0])] = 1
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            for k in range(K):
                if dp[i-1][j][k]:
                    dp[i][j][k+d]=1
                    dp[i][j][abs(k-d)]=1
        if j-1>=0:
            for k in range(K):
                if dp[i][j-1][k]:
                    dp[i][j][k+d] = 1
                    dp[i][j][abs(k-d)]=1
for k in range(K):
    if dp[i][j][k]:
        print(k)
        exit()



### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
# a=[set() for j in range(w)]
K=160*80
dp = [[0]*w for i in range(h)]
dp[0][0]=1<<K
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            dp[i][j] |= dp[i-1][j]
        if j-1>=0:
            dp[i][j] |= dp[i][j-1]
        dp[i][j] = (dp[i][j]<<d) | (dp[i][j]>>d)


ans = K
for i in range(2*K):
    if dp[h-1][w-1]  & (1 << i)>0:
        ans = min(ans,abs(K-i))
print(ans)
# for di in dp:
#     print(di)
### BUGGY CODE ###

N, M =map(int, input().split())
Ps =[]
Ys =[]
dic = {}
for i in range(M):
    p, y = map(int, input().split())
    Ps.append(p)
    Ys.append(y)
    ls = dic.get(p, [])
    ls.append(y)
    dic[p] = ls
for p in Ps:
    ls = dic[p]
    ls.sort()
    dic[p] = ls
for i in range(M):
    p = Ps[i]
    y = Ys[i]
    number = dic[p].index(y) + 1
    strp = str(p)
    strn = str(number)
    print(strp.zfill(6) + strn.zfill(6))


### FIXED CODE ###

N, M =map(int, input().split())
ls = []
pcount =[]
for i in range(N):
    pcount.append(0)
for i in range(M):
    p, y = map(int, input().split())
    ls.append([i, p, y])
ls.sort(key = lambda x:x[2])

for l in ls:
    pcount[l[1]-1] += 1
    l.append(pcount[l[1]-1])
ls.sort(key = lambda x:x[0])
for l in ls:
    print(str(l[1]).zfill(6) + str(l[3]).zfill(6))
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()
for _ in range(q):
    l,r = map(int, input().split())
    s = S[l-1:r]
    print(s.count('AC'))

### FIXED CODE ###

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

N = int(input())
L = sorted(list(map(int, input().split())))


def f(v):
    left = 0
    right = N
    while left + 1 < right:
        x = (left + right) // 2
        if v > L[x]:
            left = x
        else:
            right = x
    return right


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        idx = f(L[i] + L[j])
        # print('a, b, idx', a, b, idx)
        # idx = np.searchsorted(L, a + b, sorter=None)
        ans += idx - 1 - j
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=neg
        ret+=zzz
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = -1
Ri = len(x) - 1
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    tmp = 0
    for uk in UorD:
        cumsum += uk
        cnt_sum[cumsum + n] += 1
        tmp += sum(cnt_sum[:cumsum + n])
        if tmp >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Ri])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
P = [0]+list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    for j in range(0, i+1):
        if j > 0:
            dp[i][j] = P[i]*dp[i-1][j-1]+(1-P[i])*dp[i-1][j]
        else:
            dp[i][j] = (1-P[i])*dp[i-1][j]

ans = 0
for i in range(N//2+1, N+1):
    ans += dp[-1][i]
print(ans)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
P = [0]+list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    for j in range(0, i+1):
        if j > 0:
            dp[i][j] = P[i]*dp[i-1][j-1]+(1-P[i])*dp[i-1][j]
        else:
            dp[i][j] = (1-P[i])*dp[i-1][j]

ans = 0
for i in range(N//2+1, N+1):
    ans += dp[-1][i]
print(ans)
### BUGGY CODE ###

import itertools
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans+=gcd(i,j,k)
print(ans)


### FIXED CODE ###

import itertools
import math
from functools import reduce
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    t=math.gcd(i,j)
    for k in range(1,K+1):
      ans+=math.gcd(t,k)
print(ans)
### BUGGY CODE ###

# 無限回試行できる時、Kの最小値を最大化する問題
s = input()
now = s[0]
cnt = 1
use = []
for i in range(1,len(s)):
    if now == s[i]:
        cnt += 1
    else:
        use.append(cnt)
        cnt = 1
        now = s[i]
use.append(cnt)

min_prob = len(s)
def ketsugou(l):
    global min_prob
    #一番小さいやつをくっつけていく
    m = l.index(min(l))
    if m == 0 or m == len(l) - 1:
        s1 = l[m]
        s2 = sum(l) - l[m]
        min_prob = min(min_prob, max(s1, s2))
        if m == 0:
            l.pop(0)
            l[0] += s1
        else:
            l.pop()
            l[-1] += s1
    else:
        s1 = sum(l[:m + 1])
        s2 = sum(l[:m])
        s3 = sum(l[m:])
        s4 = sum(l[m+1:])
        min_prob = min(min_prob, max(s1, s2,s3,s4))
        if l[m - 1] < l[m + 1]:
            l[m - 1] += l[m]
        else:
            l[m + 1] += l[m]
        l.pop(m)
while(len(use) > 1):
    ketsugou(use)
print(min_prob)


### FIXED CODE ###

# 無限回試行できる時、Kの最小値を最大化する問題
s = input()
now = s[0]
cnt = 1
use = []
for i in range(1,len(s)):
    if now == s[i]:
        cnt += 1
    else:
        use.append(cnt)
        cnt = 1
        now = s[i]
use.append(cnt)

min_prob = len(s)
sum_s = sum(use)
def ketsugou(l):
    global min_prob
    global sum_s
    #一番小さいやつをくっつけていく
    m = l.index(min(l))
    if m == 0 or m == len(l) - 1:
        s1 = l[m]
        s2 = sum_s - l[m]
        min_prob = min(min_prob, max(s1, s2))
        if m == 0:
            l = l[1:]
            l[0] += s1
        else:
            l.pop()
            l[-1] += s1
    else:
        s1 = sum(l[:m])
        s2 = s1 + l[m]
        s3 = sum_s - s1
        s4 = sum_s - s2
        min_prob = min(min_prob, max(s1, s2,s3,s4))
        if l[m - 1] < l[m + 1]:
            l[m - 1] += l[m]
        else:
            l[m + 1] += l[m]
        l.pop(m)
#while(len(use) > 1):
#    ketsugou(use)
sum_ss = 0
for i in range(len(use)):
    sum_ss += use[i]
    min_prob = min(min_prob, max(sum_s - sum_ss, sum_ss))

print(min_prob)
### BUGGY CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)
#print(tblpow)
#1 10 9 12 3 4

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
### BUGGY CODE ###

# abc152

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

ans = n
for i in range(n):
    if min(lists[:i+1]) != lists[i]:
        ans -= 1
print(ans)

### FIXED CODE ###

# abc152

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

std = lists[0]
ans = 1

for i in range(1,n):
    if lists[i] < std:
        ans += 1
        std = lists[i]
        
print(ans)
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])


### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in l:
  if i[0] == n:
    c.append(i[1])
    l.remove(i)
  elif i[1] == n:
    c.append(i[0])
    l.remove(i)
  elif 1 in i:
    continue
  else:
    l.remove(i)
    
for i in range(len(l)):
  if l[i][0] == 1:
    if l[i][1] in c:
      print('POSSIBLE')
      exit()
  if l[i][1] == 1:
    if l[i][0] in c:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
c = [[] for _ in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  c[a].append(b)
  c[b].append(a)

for i in c[1]:
  if n in c[i]:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

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

l = len(S)
nAB = [0]*(l+1)
nA = [0]*(l+1)
nB = [0]*(l+1)
nC = [0]*(l+1)
nABC = [0]*(l+1)

q = 0
for i,s in enumerate(S):
    if s == '?':
        nA[i+1] = 3*nA[i] + (3**q % MOD)
        nB[i+1] = 3*nB[i] + (3**q & MOD)
        nC[i+1] = 3*nC[i] + (3**q & MOD)
        nAB[i+1] = 3*nAB[i] + nA[i]
        nABC[i+1] = 3*nABC[i] + nAB[i]
        q += 1
    if s == 'A':
        nA[i+1] = nA[i] + (3**q % MOD)
        nB[i+1] = nB[i]
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i]
    if s == 'B':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i] + (3**q % MOD)
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i] + nA[i]
        nABC[i+1] = nABC[i]
    if s == 'C':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i]
        nC[i+1] = nC[i] + (3**q % MOD)
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i] + nAB[i]
    nA[i+1] = nA[i+1] % MOD
    nB[i+1] = nB[i+1] % MOD
    nC[i+1] = nC[i+1] % MOD
    nAB[i+1] = nAB[i+1] % MOD
    nABC[i+1] = nABC[i+1] % MOD

print(nABC[l] % MOD)



### FIXED CODE ###

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

l = len(S)
nAB = [0]*(l+1)
nA = [0]*(l+1)
nB = [0]*(l+1)
nC = [0]*(l+1)
nABC = [0]*(l+1)

add = 1
for i,s in enumerate(S):
    if s == '?':
        nA[i+1] = 3*nA[i] + add
        nB[i+1] = 3*nB[i] + add
        nC[i+1] = 3*nC[i] + add
        nAB[i+1] = 3*nAB[i] + nA[i]
        nABC[i+1] = 3*nABC[i] + nAB[i]
        add = (add * 3) % MOD
    if s == 'A':
        nA[i+1] = nA[i] + add
        nB[i+1] = nB[i]
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i]
    if s == 'B':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i] + add
        nC[i+1] = nC[i]
        nAB[i+1] = nAB[i] + nA[i]
        nABC[i+1] = nABC[i]
    if s == 'C':
        nA[i+1] = nA[i]
        nB[i+1] = nB[i]
        nC[i+1] = nC[i] + add
        nAB[i+1] = nAB[i]
        nABC[i+1] = nABC[i] + nAB[i]
    nA[i+1] = nA[i+1] % MOD
    nB[i+1] = nB[i+1] % MOD
    nC[i+1] = nC[i+1] % MOD
    nAB[i+1] = nAB[i+1] % MOD
    nABC[i+1] = nABC[i+1] % MOD

print(nABC[l] % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
total=sum(A)
for i in range(Q):
    B, C = map(int, input().split())
    x=A.count(B)
    if x>0:
        total=total-B*x+C*x
        A.extend([C]*x)
    print(total)



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
total=sum(A)
A=Counter(A)
for i in range(Q):
    B, C = map(int, input().split())
    total=total-(A[B]*B)+(C*A[B])
    A[C] = A[C]+A[B]
    A[B]=0
    print(total)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools


def change(val):
    # 黒なら1
    if val == '#':
        return 1

    # 白なら0
    return 0


# def calc_root(board):


def main():
    h, w = map(int, input().split())
    board = [[change(s) for s in input()] for i in range(h)]

    cnt = 200
    for move in itertools.product(range(0, 2), repeat=h + w - 2):

        if sum(move) != h - 1:
            continue

        x, y, z = 0, 0, board[0][0]
        temp_root = [(x, y, z)]
        change_cnt = 0
        if board[y][x] == 1:
            change_cnt += 1

        x_cnt = 0
        y_cnt = 0
        sum_x_cnt = 1
        sum_y_cnt = 1
        for hko in move:
            now_z = 0
            # 0なら横移動
            if hko == 0:
                x += 1
                now_z = board[y][x]
                if now_z == 1:
                    x_cnt += 1
                else:
                    x_cnt = 0
                y_cnt = 0
            else:
                y += 1
                now_z = board[y][x]
                if now_z == 1:
                    y_cnt += 1
                else:
                    y_cnt = 0
                x_cnt = 0

            sum_x_cnt = max(sum_x_cnt, x_cnt)
            sum_y_cnt = max(sum_y_cnt, y_cnt)
            z += now_z
            temp_root.append((x, y, z))

        cnt = min(cnt, z - sum_x_cnt - sum_y_cnt + 2)

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools


def change(val):
    # 黒なら1
    if val == '#':
        return 1

    # 白なら0
    return 0


# def calc_root(board):


def main():
    h, w = map(int, input().split())
    board = [[s for s in input()] for i in range(h)]

    cnt = 200
    dp = [[200] * w for i in range(h)]

    for i_row, row in enumerate(dp):
        for i_col, col in enumerate(row):
            if i_row == 0 and i_col == 0:
                dp[i_row][i_col] = change(board[i_row][i_col])
                continue

            if i_row >= 1:
                if board[i_row][i_col] == '#' and board[i_row - 1][i_col] == '.':
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col], dp[i_row][i_col])

            if i_col >= 1:
                if board[i_row][i_col] == '#' and board[i_row][i_col - 1] == '.':
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1], dp[i_row][i_col])

    print(dp[-1][-1])


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

n, q = map(int, input().split())
b = input()
a = [[int(x) for x in input().split()] for _ in range(q)]
ans=[0]
for j in range(len(b)-1):
        if b[j] == "A" and b[j+1] == "C":
            ans.append(1)
        else:
            ans.append(0)
for i in a:
    print(sum(ans[i[0]:i[1]]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [[int(x) for x in input().split()] for _ in range(q)]
add_list = [0]
for i in range(len(s)-1):
    if s[i:i+2] == "AC":
        add_list.append(add_list[i]+1)
    else:
        add_list.append(add_list[i])
for i in t:
    ans = add_list[i[1]-1] - add_list[i[0]-1]
    print(ans)