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

import sys
input = sys.stdin.readline

H, W = (int(i) for i in input().split())
#e = [[i for i in input().split()] for i in range(H)]
e = []
for x in range(H):
    e.append(list(input()))

maxcount = 1
for i in range(H):
    for j in range(W):
        #print("start", i, j)
        count = 1
        if e[i][j] == "#":
            continue
        for k in range(i+1, H):
            #print(e[k][j], k, j)
            if e[k][j] == "#":
                #print(k, j)
                break
            else:
                count +=1
        #print("1 ", count)
        for l in range(1, i+1):
            #print(e[i-l][j], i-l, j)
            if e[i-l][j] == "#":
                break
            else:
                count += 1
        #print("2 ", count)
        if count + W -1 < maxcount:
            continue
        for m in range(j+1, W):
            if e[i][m] == "#":
                break
            else:
                count +=1
        #print("3 ",count)
        for n in range(1, j+1):
            if e[i][j-n] == "#":
                break
            else:
                count +=1
        if maxcount < count:
            maxcount = count
        if maxcount == W+H:
            break
    else:
        continue
    break
print(maxcount)


### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = (int(i) for i in input().split())
#e = [[i for i in input().split()] for i in range(H)]
e = []
for x in range(H):
    e.append(list(input()))

L = [[0] * W for i in [1] * H]
R = [[0] * W for i in [1] * H]
D = [[0] * W for i in [1] * H]
U = [[0] * W for i in [1] * H]
totalmax = 0

for i in range(H):
    for j in range(W):
        if e[i][j] == ".":
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        if e[i][W-1-j] == ".":
            #print(i, W-1-j)
            if W-1-j == W-1:
                R[i][W-1-j] = 1
            else:
                R[i][W-1-j] = R[i][W-j] + 1
                #print(R[i][W-j-2])
            #print(R[i][W-j-1])
        if e[i][j] == ".":
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
        if e[H-1-i][j] == ".":
            if H-1-i == H-1:
                D[H-1-i][j] = 1
            else:
                D[H-1-i][j] = D[H-i][j] + 1

for i in range(H):
    #print("")
    for j in range(W):
        totalmax = max(totalmax, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
        #print(L[i][j],R[i][j], D[i][j], U[i][j], end="/")



print(totalmax)
### BUGGY CODE ###

n,W,*wv=map(int,open(0).read().split())
w=wv[::2]
v=wv[1::2]
dp=[[0 for i in range(W+1)]for j in range(2)]
for i in range(n):
  t=i&1
  for j in range(W+1):
    if j<w[i]:
      dp[t][j]=dp[t-1][j]
    else:
      dp[t][j]=max(dp[t-1][j-w[i]]+v[i],dp[t-1][j])
print(dp[(n-1)&1][-1])

### FIXED CODE ###

import numpy as np
n,W,*wv=map(int,open(0).read().split())
w=np.array(wv[::2])
v=np.array(wv[1::2])
dp=np.zeros([n+1,W+1],dtype=int)
for i in range(1,n+1):
  now=np.zeros(W+1,dtype=int)
  now[w[i-1]:]=dp[i-1][:-w[i-1]]+v[i-1]
  dp[i]=np.maximum(dp[i-1],now)
print(dp[-1][-1])
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

ans = 0
for i in range(A, B+1):
    if i%C!=0 and i%D!=0:
        ans+=1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A, B, C, D = map(int, input().split())

N = B - A + 1

g = lcm(C,D)
C_ = B//C - (A-1)//C
D_ = B//D - (A-1)//D
CD_ = B//g - (A-1)//g
ans = N - C_ - D_ + CD_
print(ans)
### BUGGY CODE ###

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

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

A = []
B = []
C = []

def s_(x):
    t = 0
    for i in range(x+1):
        t += i
    return t / x


for i in P:
    if i not in A:
        A.append(i)
        B.append(s_(i))
        C.append(B[-1])
    else:
        C.append(B[A.index(i)])
max_ = 0
for j in range(n - k + 1):
    g = sum(C[j:j+k])
    if max_< g:
        max_ = g
print(max_)

### FIXED CODE ###

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

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

B = []
t = -1
init_sum = sum(A[0:k])

for i in range(n - k+1):
    if t < init_sum:
        B = A[i:i+k]
        t = init_sum
    if i != n - k:
        init_sum = init_sum - A[i] + A[i+k]


import collections
B = sorted(B)
C = collections.Counter(B)

D = list(C.keys())
E = list(C.values())
F = zip(D, E)
F = sorted(F)
D, E = zip(*F)

G = []
j = 0
total = 0
for i in range(max(D) + 1):
    total += i
    if D[j] == i:
        G.append(total)
        j += 1
ans = 0
k = 0
for i, j in zip(D, G):
    ans += (j/i) * E[k]
    k += 1
print(ans)
### BUGGY CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, a: str):
    # a = "11002102121200"
    # a = "210211"
    a = list(map(int,a))
    # new = []
    # for i in range(len(a)-1):
    #     new.append(abs(a[i]-a[i+1]))
    # a = new
    # print(a)
    while len(a) > 1:
        new = []
        for i in range(len(a)-1):
            new.append(abs(a[i]-a[i+1]))
        a = new
    print(a[0])

    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, a: str):
    a = [int(a[i])-1 for i in range(N)]
    zeroone = [a[i]%2 for i in range(N)]

    SUM = 0
    comb = [0]*N
    comb[0] = 1

    for i in range(1, N):
        comb[i] = 1 if (N-1)&i == i else 0

    for i in range(N):
        SUM += zeroone[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(1)
        return
    
    if 1 in a:
        print(0)
        return
    
    ## 0か2
    zerotwo = [a[i]//2 for i in range(N)]

    SUM = 0
    for i in range(N):
        SUM += zerotwo[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(2)
        return
    
    print(0)
    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

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

import bisect

if __name__ == '__main__':
    def check(mid):
        count = 0
        for i in range(n):
            position = bisect.bisect_left(a, (mid - a[i]))
            count += (n - position)
        return count < m


    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    # 左手でa[i]の手を握るとする
    # a[i]を持っているときに和がx未満になるときの右手の数字はx - a[i]未満の数字である
    # lower_bound
    # この値をNから引くことで和がx以上になるペアの個数がわかる
    # この値の合計がM未満になればそこが最大の幸福度である

    # 要するに、M個のペアを作るためには最大いくらの和を採用できるかを二分探索する

    ng = 0
    ok = 10 ** 5 * (n + 1)

    while 1 < abs(ok - ng):
        # mid -> boundとなる和。これより大きい和をもつペアをM個作れるかを判定する
        mid = (ok + ng) // 2
        c = check(mid)
        # ペアの個数がmより小さい場合は、okの範囲を下げる
        if c:
            ok = mid
        # そうでない場合はまだ余裕があるので、ngをあげる
        else:
            ng = mid

    # ここが終了した時点でngにはm個以上のペアを作るための最大のboundが入っている

    # upper_boundで左手にa[i]がある場合のng - a[i]の数を判定する
    # ansに求めた数 * a[i] + 右手に持つ幸福度の総和を足す
    # mから求めた数を引く

    ans = 0
    sum_array = [0] * (n + 1)
    # 累積和で高速化をする
    # (x + a[i]) + (x + a[i + 1) + (x + a[i + 2]).....
    #   -> (x * 個数) * (a[i] + a[i + 1] + a[i + 2])

    for i in range(n):
        sum_array[i + 1] = sum_array[i] + a[i]
    for i in range(n):
        position = bisect.bisect_right(a, ng - a[i])
        ans += (n - position) * a[i] + sum_array[n] - sum_array[position]
        m -= (n - position)

    ans += ng * m
    print(ans)


### FIXED CODE ###

import bisect

if __name__ == '__main__':
    def check(mid):
        count = 0
        for i in range(n):
            position = bisect.bisect_left(a, (mid - a[i]))
            count += (n - position)
        return count < m


    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    # 左手でa[i]の手を握るとする
    # a[i]を持っているときに和がx未満になるときの右手の数字はx - a[i]未満の数字である
    # lower_bound
    # この値をNから引くことで和がx以上になるペアの個数がわかる
    # この値の合計がM未満になればそこが最大の幸福度である

    # 要するに、M個のペアを作るためには最大いくらの和を採用できるかを二分探索する

    ng = 0
    ok = 10 ** 5 * (n + 1)

    while 1 < abs(ok - ng):
        # mid -> boundとなる和。これより大きい和をもつペアをM個作れるかを判定する
        mid = (ok + ng) // 2
        c = check(mid)
        # ペアの個数がmより小さい場合は、okの範囲を下げる
        if c:
            ok = mid
        # そうでない場合はまだ余裕があるので、ngをあげる
        else:
            ng = mid

    # ここが終了した時点でngにはm個以上のペアを作るための最大のboundが入っている

    # upper_boundで左手にa[i]がある場合のng - a[i]の数を判定する
    # ansに求めた数 * a[i] + 右手に持つ幸福度の総和を足す
    # mから求めた数を引く

    ans = 0
    sum_array = [0] * (n + 1)
    # 累積和で高速化をする
    # (x + a[i]) + (x + a[i + 1) + (x + a[i + 2]).....
    #   -> (x * 個数) * (a[i] + a[i + 1] + a[i + 2])

    for i in range(n):
        sum_array[i + 1] = sum_array[i] + a[i]
    for i in range(n):
        position = bisect.bisect_right(a, ng - a[i])
        ans += (n - position) * a[i] + sum_array[n] - sum_array[position]
        m -= (n - position)

    ans += ng * m
    print(ans)
### BUGGY CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
for i in range(len(s)):
  r += s[-i-1]*(10**i)
  r %= 2019
  d[r] += 1
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)


### FIXED CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

def solve():
  h,w,n = (int(i) for i in input().split())
  
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    d = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
    for dx,dy in d:
      if 2 <= a+dx <= h-1 and 2 <= b+dy <= w-1:
        query.append((a+dx,b+dy))
  ans = [0]*10
  #print(query)
  for i in range(2,h):
    for j in range(2,w):
      #print("aa",i,j)
      tp = query.count((i,j))
      #print(tp)
      ans[tp] += 1
  for i in ans:
    print(i)
solve()


### FIXED CODE ###

import collections 
def solve():
  h,w,n = (int(i) for i in input().split())
  
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    d = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
    for dx,dy in d:
      if 2 <= a+dx <= h-1 and 2 <= b+dy <= w-1:
        query.append((a+dx,b+dy))
  ans = [0]*10
  if query:
   query = collections.Counter(query)
   values, counts = zip(*query.most_common())
   for i in range(10):
     ans[i] = counts.count(i)
  tp = sum(ans)
  ans[0] = (h-2)*(w-2)-tp
  
  for i in ans:
    print(i)
solve()
### BUGGY CODE ###

# ABC153e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

    h, n = map(int, input().split())
    maho = []
    for _ in range(n):
        maho.append(list(map(int, input().split())))

    # dp[i][j]=i番目までの魔法でモンスターの体力をj減らすためにつかう魔力の最小値
    # dp[i][j]=min(dp[i-1][j],dp[i][j-maho[i][0]])+maho[i][1]

    dp = [[10 ** 12] * (h + 1) for _ in range(3)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + 1):
            if j == 0:
                dp[(i + 1) % 3][0] = 0
            dp[(i + 1) % 3][j] = min(dp[i % 3][j],
                                     dp[(i + 1) % 3][max(0, j - maho[i][0])] + maho[i][1])
    print(dp[n % 3][h])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# ABC153e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

    h, n = map(int, input().split())
    maho = []
    for _ in range(n):
        maho.append(list(map(int, input().split())))

    # dp[i][j]=i番目までの魔法でモンスターの体力をj減らすためにつかう魔力の最小値
    # dp[i][j]=min(dp[i-1][j],dp[i][j-maho[i][0]])+maho[i][1]

    dp = [[10 ** 12] * (h + 1) for _ in range(3)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + 1):
            if j == 0:
                dp[(i + 1) % 3][0] = 0
            dp[(i + 1) % 3][j] = min(dp[i % 3][j],
                                     dp[(i + 1) % 3][max(0, j - maho[i][0])] + maho[i][1])
    print(dp[n % 3][h])


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

import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            ans = fractions.gcd(a,b)
            cnt += 6*ans
            for c in range(b+1,K+1):
                cnt += 6*fractions.gcd(ans, c)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)

### FIXED CODE ###

import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    dict_ = {}
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            if '{}_{}'.format(a,b) in dict_:
                ans = dict_['{}_{}'.format(a,b)]
            else:
                ans = fractions.gcd(a,b)
                dict_['{}_{}'.format(a,b)] = ans
            cnt += 6*ans
            for c in range(b+1,K+1):
                if '{}_{}'.format(ans,c) in dict_:
                    _ans = dict_['{}_{}'.format(ans,c)]
                else:
                    _ans = fractions.gcd(ans, c)
                    dict_['{}_{}'.format(ans,c)] = _ans
                cnt += 6*_ans
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)
### BUGGY CODE ###

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

for i in range(A, B+1):
    if abs(i-A) < K or abs(B-i) < K:
        print(i)


### FIXED CODE ###

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

R = [A, B]

for k in range(1, K):
    if A + k >= B:
        break
    R.append(A + k)

for k in range(1, K):
    if B - k <= A:
        break
    R.append(B - k)


R = list(set(R))
R.sort()

for r in R:
    print(r)
### BUGGY CODE ###

import itertools
L,R=map(int,input().split())

A=[]
D=[]

for i in range(R-L+1):
    A.append((i+L)%2019)
B=sorted(A)
C=list(itertools.combinations(A,2))
for j in range(len(C)):
    D.append(C[j][0]*C[j][1]%2019)
E=sorted(D)
print(E[0])


### FIXED CODE ###

import itertools
L,R=map(int,input().split())

A=[]
D=[]

if R-L+1<2019:
    for i in range(R-L+1):
        A.append((i+L)%2019)

    if A.count(1)>=2:
        B=set(A)
        B.add(1)
    else:
        B=set(A)

    C=list(itertools.combinations(B,2))
    for j in range(len(C)):
        D.append(C[j][0]*C[j][1]%2019)
    E=sorted(D)
    print(E[0])
else:
    print(0)
### BUGGY CODE ###

n = int(input())
b = 0
def div(n):
    for k in range(2,n+1):
        if n % k == 0:
            return k
    return 1

def pf(n):
    pf=[]
    while n != 1:
        pf.append(div(n))
        n = n // div(n)
    #p = list(set(pf))
    return pf

for c in range(1,n):
    m = n - c #mの約数を数える
    insu = pf(m)
    insu2 = list(set(insu))
    l = len(insu2)
    d = 1
    for j in range(l):
        k = insu.count(insu2[j]) + 1
        d = k * d
    b += d

print(b)



### FIXED CODE ###

n = int(input())
count = 0
for a in range(1,n):
    b = (n-1) // a
    count += b

print(count)
### BUGGY CODE ###

n=int(input())
s=[""]*n
st=set()
r=0
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  s[ii]=ss
  st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

tp=[]
ii=0
for sss in st:
  c=s.count(sss)
  if c>1:
    tp.append(c)
    r+=(c*(c-1))//2
    
print(r)

### FIXED CODE ###

n=int(input())
s=[""]*n
st=set()
d={}
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  if ss in st:
    d[ss]+=1
  else:
    d[ss]=1
    st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

r=0
for sss in st:
  c=d[sss]
  if c>1:
    r+=(c*(c-1))//2
    
print(r)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort(reverse=True)
for _ in range(n):
    a.pop(0)
    ans+=a.pop(0)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=sum(a[n::2])
print(ans)
### BUGGY CODE ###

N, a, b = map(int, input().split()); a -= 1; b -= 1
P = []
Q = []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x-y, x+y, i))
    Q.append((x+y, x-y, i))

d = max(abs(P[a][0] - P[b][0]), abs(P[a][1] - P[b][1]))

*parent, = range(N)
def root(x):
    if x == parent[x]:
        return x
    y = parent[x] = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
C = [0]*N
D = [0]*N

def solve(P0):
    P = P0[:]
    P.sort()

    s = t = 0
    for i in range(N):
        x, y, i0 = P[i]
        while t < N and P[t][0] < x-d or (P[t][0] == x-d and P[t][1] <= y+d): t += 1
        while s < N and (P[s][0] < x-d or (P[s][0] == x-d and P[s][1] < y-d)): s += 1
        for j in range(s, t):
            j0 = P[j][2]
            unite(i0, j0)
            if abs(P0[i0][0] - P0[j0][0]) == abs(P0[i0][1] - P0[j0][1]):
                D[i0] += 1
            else:
                C[i0] += 1
solve(P)
solve(Q)

S = T = 0
r = root(a)
for i in range(N):
    if root(i) == r:
        S += C[i]; T += D[i]
print(S + T//2)


### FIXED CODE ###

N, a, b = map(int, input().split()); a -= 1; b -= 1
P = []
Q = []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x-y, x+y, i))
    Q.append((x+y, x-y, i))

d = max(abs(P[a][0] - P[b][0]), abs(P[a][1] - P[b][1]))

*parent, = range(N)
def root(x):
    if x == parent[x]:
        return x
    y = parent[x] = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
C = [0]*N
D = [0]*N

def check(P0, i0, j0):
    return abs(P0[i0][0] - P0[j0][0]) == abs(P0[i0][1] - P0[j0][1])

def solve(P0):
    P = P0[:]
    P.sort()

    s = t = 0; prev = -1
    for i in range(N):
        x, y, i0 = P[i]
        while t < N and P[t][0] < x-d or (P[t][0] == x-d and P[t][1] <= y+d): t += 1
        while s < N and (P[s][0] < x-d or (P[s][0] == x-d and P[s][1] < y-d)): s += 1
        if s < t:
            j0 = P[s][2]
            unite(i0, j0)
            if check(P0, i0, j0):
                D[i0] += 1
            else:
                C[i0] += 1
            if s < t-1:
                j0 = P[t-1][2]
                if check(P0, i0, j0):
                    D[i0] += 1
                    C[i0] += t-s-2
                else:
                    C[i0] += t-s-1
            for j in range(max(prev, s), t-1):
                unite(P[j][2], P[j+1][2])
            prev = t-1
solve(P)
solve(Q)

S = T = 0
r = root(a)
for i in range(N):
    if root(i) == r:
        S += C[i]; T += D[i]
print(S + T//2)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
def findb(ind,checker):
    global count
    b = S[ind:].count("B")
    if ind + checker < N:
        if S[ind+checker] == "B":
            b -= 1
    if b > 0:
        count += b
def findg(ind,checker):
    global count
    g = S[ind:].count("G")
    if ind + checker < N:
        if S[ind+checker] == "G":
            g -= 1
    if g > 0:
        count += g
def findr(ind,checker):
    global count
    r = S[ind:].count("R")
    if ind + checker < N:
        if S[ind+checker] == "R":
            r -= 1
    if r > 0:
        count += r
for i in range(N):
    if S[i] == "R":
        for j in [x for x, y in enumerate(S[i:]) if y == 'G']:
            findb(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'B']:
            findg(i+j,j)
    elif S[i] == "G":
        for j in [x for x, y in enumerate(S[i:]) if y == 'B']:
            findr(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'R']:
            findb(i+j,j)
    else:
        for j in [x for x, y in enumerate(S[i:]) if y == 'R']:
            findg(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'G']:
            findr(i+j,j)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

import numpy as np

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

"""
import random
base_list = ['A', 'T', 'C', 'G']
S = ''
N = int(1e5)
Q = 1
A = [[100, 900]]
for i in range(N):
  S += random.choice(base_list)
"""

L_cnt = np.zeros(N-1)
L_cnt[0] = 0
L_str = S[0]
R_cnt = np.zeros(N-1)
R_cnt[0] = 0
R_str = S[N-1]

for i in range(N-2):
  #L_str = L_str + S[i+1]
  #L_cnt[i+1] = L_cnt[i] + (L_str[-2:] == 'AC')
  #R_str = S[N-2-i] + R_str
  #R_cnt[i+1] = R_cnt[i] + (R_str[:2] == 'AC')
  #print(i, L_str)
  #print(i, R_str)
  #L_str = S[i] + S[i+1]
  #L_cnt[i+1] = L_cnt[i] + (L_str == 'AC')
  #R_str = S[N-2-i] + S[N-1-i]
  #R_cnt[i+1] = R_cnt[i] + (R_str == 'AC')
  L_str = S[i] + S[i+1]
  L_cnt[i+1] = (L_str == 'AC')
  R_str = S[N-2-i] + S[N-1-i]
  R_cnt[i+1] = (R_str == 'AC')

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
for i in range(Q):
  #ans = n_whole - (L_cnt[A[i][0]-1] + R_cnt[N-A[i][1]])
  ans = n_whole - (sum(L_cnt[:A[i][0]]) + sum(R_cnt[:N-A[i][1]+1]))
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""



### FIXED CODE ###

import numpy as np

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

"""
import random
base_list = ['A', 'T', 'C', 'G']
S = ''
N = int(1e5)
Q = 1
A = [[100, 900]]
for i in range(N):
  S += random.choice(base_list)
"""

L_cnt = np.zeros(N-1)
R_cnt = np.zeros(N-1)

for i in range(N-2):
  L_cnt[i+1] = (S[i:i+2] == 'AC')
  R_cnt[i+1] = (S[N-2-i:N-i] == 'AC')

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
L_cumsum = np.array(L_cnt).cumsum()
R_cumsum = np.array(R_cnt).cumsum()
for i in range(Q):
  ans = n_whole - (L_cumsum[A[i][0]-1] + R_cumsum[N-A[i][1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""