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

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

for i in range(1,n+1):
    cnt=0
    for j in range(1,42):
        for k in range(1,42):
            for l in range(1,42):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    cnt+=1
                    break
                elif j**2+k**2+l**2+j*k+k*l+l*j>i:
                    break
    print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n)
for j in range(1,n+1):
    for k in range(1,n+1):
        for l in range(1,n+1):
            if j**2+k**2+l**2+j*k+k*l+l*j>n:
                break
            else:
                a[j**2+k**2+l**2+j*k+k*l+l*j-1]+=1

for i in a:
    print(i)
### BUGGY CODE ###

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


def quick(a):
    if len(a) < 2:
        return a
    p = a[0]
    x, y = quick_div(p, a[1:])
    return quick(x) + [p] + quick(y)


def quick_div(p, a):
    if len(a) < 1:
        return ([], [])
    x, y = quick_div(p, a[1:])
    if a[0] < p:
        return ([a[0]] + x, y)
    else:
        return (x, [a[0]] + y)


h = quick(h)
# print(h)
dh = []
for i in range(len(h) - K + 1):
    dh = dh + [h[i + K - 1]-h[i]]

print(min(dh))

# 入力例1
# 5 3
# 5
# 7
# 5
# 7
# 7

# 出力
# 2


### FIXED CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for _ in range(N)])
print(min([h[i+K-1]-h[i] for i in range(N - K + 1)]))
### BUGGY CODE ###

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

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

Swap=[None]*M

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break

        if judge_2==0:
            i+=1
        else:
            judge_2=0


Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


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

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

# T[i]に1からiまでの合計値が入っている
# M[i]にiの目があるさいころの期待値が入っている
# T = [0]
# M = [0]
# for j in range(1,1001):
#     T.append(j + T[j-1])
#     K.append(T[j]/j)
# 計算すると(n+1)/2


# M = [0]
# for j in range(1,1001):
#     M.append((j+1)/2)
# # print(K)

# PP = []
# for k in P:
#     PP.append(M[k])
# TEMP = []
ANS = 0
for i in range(N-K+1):
    # TEMP.append(sum(P[i:i+K]))
    TEMP = sum(P[i:i+K])
    if TEMP > ANS:
        ANS = TEMP
# ANS = max(TEMP)
print((ANS+K)/2)



### FIXED CODE ###

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

# T[i]に1からiまでの合計値が入っている
# M[i]にiの目があるさいころの期待値が入っている
# T = [0]
# M = [0]
# for j in range(1,1001):
#     T.append(j + T[j-1])
#     K.append(T[j]/j)
# 計算すると(n+1)/2


# M = [0]
# for j in range(1,1001):
#     M.append((j+1)/2)
# # print(K)

# PP = []
# for k in P:
#     PP.append(M[k])
# TEMP = []
ANS = 0
for i in range(N-K+1):
    # TEMP.append(sum(P[i:i+K]))
    if i == 0:
        TEMP = sum(P[i:i+K])
    else:
        TEMP = TEMP - P[i-1] + P[i+K-1]
    if TEMP > ANS:
        ANS = TEMP
# ANS = max(TEMP)
print((ANS+K)/2)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
d=[0]*(n+1)
d[0]=1 
if 1 in a:
  d[1]=0
else:
  d[1]=1
for i in range(2,n+1):
  if i not in a:
    d[i]=(d[i-1]+d[i-2])%mod
print(d[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
d=[mod]*(n+1)
d[0]=1;d[1]=1
for i in a:
  d[i]=0
for i in range(2,n+1):
  d[i]=min(d[i],(d[i-1]+d[i-2])%mod)
print(d[n])
### BUGGY CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])


### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

N,M=[int(s) for s in input().split()] 
hito=[-1 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=[start]
  hito[start]=1
  while reach:
    _from=reach.pop(-1)
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==-1:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==-1:
    ans.add(dfs(h))
print(max(ans))

### FIXED CODE ###

N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=set()
  reach.add(start)
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.add(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))
### BUGGY CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(h)]
b=[list(map(int,input().split()))for i in range(h)]
c=[[abs(a[i][j]-b[i][j])for j in range(w)]for i in range(h)]
d=[[[]for i in range(w+1)]for j in range(h+1)]
def f(x,y):
    if x==1 and y==1:
        d[1][1]=list(set([-c[0][0],c[0][0]]))
    else:
        a=set(d[x-1][y]+d[x][y-1])
        e=set()
        for i in a:
            e.add(i-c[x-1][y-1])
            e.add(i+c[x-1][y-1])
        d[x][y]=list(e)
    if x!=h:
        f(x+1,y)
    if y!=w:
        f(x,y+1)
f(1,1)
print(abs(min(d[h][w],key=abs)))

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(h)]
b=[list(map(int,input().split()))for i in range(h)]
s=[0]*w
s[0]=p=1<<6400
for i in range(h):
    for j in range(w):
        d=abs(a[i][j]-b[i][j])
        if j>0:
            s[j]|=s[j-1]
        s[j]=(s[j]<<d)|(s[j]>>d)
t=s[-1]
for i in range(6401):
    if t&(p<<i) or t&(p>>i):
        print(i)
        break
### BUGGY CODE ###

N = int(input())
S = [*input()]
ans = 0
for left in range(N-2):
    for mid in range(left+1,N-1):
        for right in range(mid+1,N):
            if S[left]==S[mid] or S[left]==S[right] or S[mid]==S[right]:
                continue
            if mid - left == right - mid:
                continue
            ans += 1
print(ans)            
       

### FIXED CODE ###

N = int(input())
S = input()     
all = S.count("R") * S.count("G") * S.count("B")
reigai = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        k = 2 * j - i
        if k > N-1:
            break
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            reigai += 1
print(all - reigai)
### BUGGY CODE ###

h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.deepcopy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
            last_spl=i-1
        nxt_cnt=[0]*num_sp

    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

    spl_l=[]
    for aaa in range(h):
        spl_l.append(sum(tmp[:aaa]))
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = spl_l[j]
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

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

from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))

# construct graph
edges = [[] for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

# search middle edge and cut
Q = deque()
Q.append([0])
while len(Q) > 0:
    path = Q.pop()
    if path[-1] == n - 1:
        i = (len(path) - 1) // 2
        a, b = path[i], path[i + 1]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[path[-1]]:
        if v not in path:
            Q.append(path + [v])

# count Fennec's area
Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))

# construct graph
edges = [set() for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].update({j})
    edges[j].update({i})

# search middle edge and cut
Q = deque()
Q.append([0, 0])
visited = {0}
pre = {}
while len(Q) > 0:
    u, d = Q.pop()
    if u == n - 1:
        i = (d - 1) // 2
        a = u
        for _ in range(i + 1):
            b = a
            a = pre[b]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[u]:
        if v not in visited:
            pre[v] = u
            visited.update({v})
            Q.append([v, d + 1])

# count Fennec's area
Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

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

S = input()
Q = int(input())

rev = False

for i in range(Q):
    # クエリを受け取る
    query = input().split()
    # 反転の操作
    if query[0] == '1':
        if rev:
            rev = False
        else:
            rev = True
    else:
        # 追加する操作
        F = query[1]
        # 先頭に追加する場合
        if F == '1':
            # 反転しているとき
            if rev:
                # 末尾に追加
                S = S + query[2]
            # 反転していないとき
            else:
                # 先頭に追加
                S = query[2] + S
        # 末尾に追加する場合
        else:
            # 反転しているとき
            if rev:
                # 先頭に追加
                S = query[2] + S
            # 反転していないとき
            else:
                # 末尾に追加
                S = S + query[2]
if rev:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

rev = False
S1 = ''
S2 = ''

for TFC in Query:
    if TFC[0] == '1':
        rev = not rev
    else:
        if TFC[1] == '1':
            if rev:
                S2 += TFC[2]
            else:
                S1 = TFC[2] + S1
        else:
            if rev:
                S1 = TFC[2] + S1
            else:
                S2 += TFC[2]

if rev:
    print(S2[::-1] + S[::-1] + S1[::-1])
else:
    print(S1 + S + S2)
### BUGGY CODE ###

from collections import deque


class SolveE:

    def __init__(self, n, le):
        self.n = n
        self.le = le
        self.g1 = [[] for _ in range(n)]
        self.g2 = [[] for _ in range(n)]

    def add_edge(self, a, b, c):
        self.g1[a].append([b, c])

    def pre_compute(self):
        for i in range(self.n):
            d_list = [self.le + 1] * self.n
            d_list[i] = 0
            queue = deque([i])
            while len(queue) > 0:
                p = queue.popleft()
                for q, r in self.g1[p]:
                    if d_list[q] > d_list[p] + r and d_list[p] + r <= self.le:
                        d_list[q] = d_list[p] + r
                        queue.append(q)
            for j in range(self.n):
                if 0 < d_list[j] <= self.le:
                    self.g2[i].append(j)

    def query(self, s, t):
        d_list = [10000] * self.n
        d_list[s] = 0
        queue = deque([s])
        while len(queue) > 0:
            p = queue.popleft()
            for q in self.g2[p]:
                if q == t:
                    return d_list[p] + 1
                if d_list[q] > d_list[p] + 1:
                    d_list[q] = d_list[p] + 1
                    queue.append(q)
        return 0


def main():
    n, m, le = map(int, input().split())
    sol = SolveE(n, le)
    for _ in range(m):
        a, b, c = map(int, input().split())
        sol.add_edge(a - 1, b - 1, c)
        sol.add_edge(b - 1, a - 1, c)

    sol.pre_compute()

    q = int(input())
    res_list = [0] * q
    for i in range(q):
        s, t = map(int, input().split())
        res = sol.query(s - 1, t - 1)
        res_list[i] = res - 1

    for r in res_list:
        print(r)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def main():
    n, m, le = map(int, input().split())
    g1 = (le + 1) * np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c <= le:
            g1[a - 1, b - 1] = c
            g1[b - 1, a - 1] = c

    fw1 = floyd_warshall(g1, directed=False)

    g2 = 1000 * np.zeros((n, n))
    g2[fw1 <= le] = 1

    fw2 = floyd_warshall(g2, directed=False)

    q = int(input())
    res_list = [-1] * q
    for i in range(q):
        s, t = map(int, input().split())
        res = fw2[s - 1, t - 1]
        if res <= n:
            res_list[i] = int(res - 1)

    for r in res_list:
        print(r)


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

# -*- coding: utf-8 -*-

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

s = input()

for i in range(q):
    l, r  = map(int,input().split())
    a = 0
    for j in range(l-1,r-1):
        if s[j] == 'A' and s[j+1] =='C':
            a = a+1
    print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-

n, q  = map(int,input().split())
s = input()
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = map(int,input().split())


sum = [0]*(n+1)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] =='C':
        sum[i+1] = sum[i] + 1
    else:
        sum[i+1] = sum[i]

#0 1 2 3 4 5 6
# A C A C A C
# 1 2 3 4 5 6

for i in range(q):
    ans = sum[r[i]]-sum[l[i]]
    print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B=[list(map(int, input().split())) for _ in range(Q)]

ans=[]

for i in B:
  b=i[0]
  c=i[1]
  A=np.array(A)
  A=np.where(A!=b,A,c)
  
  ans.append(np.sum(A))
  
for i in ans:
  print(i)
  


### FIXED CODE ###

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

num=[0]*10**5 
a=sum(A)

for i in A: #各数字が何個あるか
  num[i-1]+=1

for _ in range(Q):
  b,c=map(int, input().split())
  
  a=a+(-num[b-1]*b+c*num[b-1])
  num[c-1]+=num[b-1]
  num[b-1]-=num[b-1]
  print(a)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
S = input()
L = [LIST() for _ in range(Q)]

for i in range(Q):
	a = S[L[i][0] - 1:L[i][1]]
	a_s = a.replace("AC", "#")
	print(len(a) - len(a_s))

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
S = input()
L = [LIST() for _ in range(Q)]

a = [0]*len(S)
for i in range(1, len(S)):
	if (S[i-1]=="A") and (S[i]=="C"):
		a[i] = a[i-1] + 1
	else:
		a[i] = a[i-1]

for i in range(Q):
	print(a[L[i][1] - 1] - a[L[i][0] - 1])
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
from math import gcd
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def divisors(n):
    m = 1
    divs = []
    while m * m <= n:
        if n % m == 0:
            divs.append(m)
            if n != m * m:
                divs.append(n // m)
        m += 1
    divs.sort()
    return divs


N, *A = map(int, read().split())
A = np.array(A)

cnt = 0
for i, a in enumerate(A):
    divs = divisors(a)[:-1]
    if len(set(divs) & set(A)) > 0:
        continue
    acc = (A == a)
    acc[i] = False
    if sum(acc) >= 1:
        continue
    cnt += 1

print(cnt)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = sorted(A)
M = pow(10, 6) + 1
divs = [False] * M
cnt = 0
for i, a in enumerate(A):
    if divs[a]:
        continue

    if i == N - 1 or a != A[i + 1]:
        cnt += 1

    acc = a
    while acc < M:
        divs[acc] = True
        acc += a
print(cnt)
### BUGGY CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
maxx = n//b
ans = 0
for i in range(min(maxx,10**8)):
    x = b*(maxx-i)-1
    ans = max(math.floor(a*x/b)-a*(math.floor(x/b)),ans)
ans = max(math.floor(a*n/b)-a*(math.floor(n/b)),ans)
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n) #上記よりxとしてmin(B-1,N)を選ぶのが最善
print((a*x)//b-a*(x//b))