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

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    # print(sy, sx)
    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()
        visited[r][c] = True

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


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

n, q = map(int, input().split())
s = input()
count = 0
ans = []
for _ in range(q):
    l, r = map(int, input().split())
    partial = s[l-1:r]

    for i in range(len(partial) - 1):
        if partial[i] and partial[i + 1]:
            if partial[i] == 'A' and partial[i + 1] == 'C':
                count += 1

    ans.append(count)
    count = 0

for a in ans:
    print(a)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)

count = 0
for i in range(n - 1):
    if s[i:i+2] == 'AC':
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]

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

S = input()
N = len(S)

def ctoi(c):
    return ord(c) - ord('a')

cums = [0]
for c in S:
    cums.append(cums[-1] ^ (1<<ctoi(c)))
if cums[-1] == 0:
    print(1)
    exit()

dp = {0:0}
for i,b in enumerate(cums):
    for k in range(26):
        msk = b^(1<<k)
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

### FIXED CODE ###

def ctoi(c):
    return ord(c) - ord('a')

def solve(s):
    masks = [1<<k for k in range(26)]
    cums = [0]
    for c in s:
        cums.append(cums[-1] ^ masks[ctoi(c)])
    if cums[-1] == 0:
        print(1)
        exit()

    dp = {0:0}
    for b in cums:
        for m in masks:
            msk = b^m
            if msk in dp:
                if b in dp:
                    dp[b] = min(dp[b], dp[msk]+1)
                else:
                    dp[b] = dp[msk]+1
    return dp[cums[-1]]

print(solve(input()))
### BUGGY CODE ###

S = input()
cnt = 0
length = len(S)
for i, s in enumerate(S):
    while(s == "A"):
        if (i+3 > length):
            break
        elif (S[i+1] == "A"):
            i += 1
        elif (S[i+1:i+3] == "BC"):
            i += 2
            cnt += 1
        else:
            break
print(cnt)


### FIXED CODE ###

S = input()
cnt = 0
length = len(S)
mem = 0
for i, s in enumerate(S):
    w = 1
    if (i < mem): continue
    while(s == "A"):
        if (i+3 > length):
            mem = i
            break
        elif (S[i+1] == "A"):
            i += 1
            w += 1
        elif (S[i+1:i+3] == "BC"):
            i += 2
            cnt += w
        else:
            mem = i
            break
print(cnt)
### BUGGY CODE ###

import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))
end = [N] * N

for _ in range(K):
    lst = [0] * N
    for i, a in enumerate(A):
        lst[max(0, i - a)] += 1
        if i + a + 1 < N:
            lst[i + a + 1] -= 1
    A = list(itertools.accumulate(lst))
    if A == end:
        break
print(*A)


### FIXED CODE ###

import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))
end = [N] * N

for _ in range(K):
    lst = [0] * N
    for i, a in enumerate(A):
        lst[max(0, i - a)] += 1
        if i + a + 1 < N:
            lst[i + a + 1] -= 1
    A = list(itertools.accumulate(lst))
    if A == end:
        break
print(*A)
### BUGGY CODE ###

int_n = int(input())

ar_int_a = []
for i in range(int_n):
    ar_int_a.append(int(input()))

numbers = set(ar_int_a)

written = [i for i in numbers if ar_int_a.count(i) % 2 == 1]

print(len(written))

### FIXED CODE ###

from collections import defaultdict


int_n = int(input())

counter = defaultdict(int)

for i in range(int_n):
    counter[int(input())] += 1

written = 0
for c in counter.values():
    if c % 2 == 1:
        written += 1


print(written)
### BUGGY CODE ###

from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    # print(visited)
    return res if sum(visited) == n else -1

inf = float('INF')
def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    e[i][k] = 0
                    e[k][j] = 0
                    e[k][i] = 0
                    e[j][k] = 0
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans if prim_heap(edge_list, n) != -1 else -1)


### FIXED CODE ###

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

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

N,M=map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

ans=0

for i in range(2 **N):
    x=0
    y=0
    z=0
    t=0

    for j in range(N):
        if ((i >> j) & 1):
            x += S[j][0]
            y += S[j][1]
            z += S[j][2]
            t += 1

    hoge = abs(x) + abs(y) + abs(z)
    if hoge > ans and t==M:
        ans=hoge

print(ans)

### FIXED CODE ###

N,M=map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]
import copy
import heapq
ans=0

for i in range(8):
    li=[]
    heapq.heapify(li)
    hoge=[1,1,1]

    for j in range(3):
        if ((i >> j) & 1):
            hoge[j]=-1
    for k in range(N):
        tmp=0
        for r in range(3):
            tmp += S[k][r] * hoge[r]
        heapq.heappush(li, tmp)
    re=0
    for t in range(M):
        re += heapq.heappop(li)

    re = abs(re)
    if re > ans :
        ans=re

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

H,W,M=map(int,input().strip().split())
h=[0 for _ in range(H)]
w=[0 for _ in range(W)]

dp=[[0 for _ in range(W)] for _ in range(H)]
for m in range(M):
    i,j=map(int,input().strip().split())
    dp[i-1][j-1]=1
    h[i-1]+=1
    w[j-1]+=1

h_max=0
hmax_l=[]
for i in range(H):
    if h_max==h[i]:
        hmax_l.append(i+1)
    elif h_max<h[i]:
        h_max=h[i]
        hmax_l=[]
        hmax_l.append(i+1)
w_max=0
wmax_l=[]
for i in range(W):
    if w_max==w[i]:
        wmax_l.append(i+1)
    elif w_max<w[i]:
        w_max=w[i]
        wmax_l=[]
        wmax_l.append(i+1)

d=True
for i in range(len(hmax_l)):
    for j in range(len(wmax_l)):
        if dp[hmax_l[i]-1][wmax_l[j]-1]==0:
            d=False
            break

ans=max(h)+max(w) if d==False else max(h)+max(w)-1
print(ans)

### FIXED CODE ###

H,W,M=map(int,input().strip().split())
h=[0 for _ in range(H)]
w=[0 for _ in range(W)]

dp=[]
for m in range(M):
    i,j=map(int,input().strip().split())
    dp.append((i,j))
    h[i-1]+=1
    w[j-1]+=1

h_max=0
hmax_l=[]
for i in range(H):
    if h_max==h[i]:
        hmax_l.append(i+1)
    elif h_max<h[i]:
        h_max=h[i]
        hmax_l=[]
        hmax_l.append(i+1)
w_max=0
wmax_l=[]
for i in range(W):
    if w_max==w[i]:
        wmax_l.append(i+1)
    elif w_max<w[i]:
        w_max=w[i]
        wmax_l=[]
        wmax_l.append(i+1)

cnt=0
for m in range(M):
    if h[dp[m][0]-1]+w[dp[m][1]-1]==h_max+w_max:
        cnt+=1

ans=h_max+w_max if cnt<len(hmax_l)*len(wmax_l) else h_max+w_max-1
print(ans)
### BUGGY CODE ###

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

xors = lambda x, y: sum([(a & x) ^ y for a in A])

def dp(flag, k):
  if k < 0: return 0

  x = 1 << k

  if flag and not(K & x):
    return xors(x, 0) + dp(True, k-1)
  else:
    return max(xors(x, x) + dp(flag, k-1), xors(x, 0) + dp(False, k-1))

print(dp(True, 40))


### FIXED CODE ###

def solve():
  N, K = map(int, input().split())
  A = [int(i) for i in input().split()]
  B = [0] * 40
  for i in range(40):
    for a in A:
      if a & (1 << i): B[i] += 1

  X = 0
  for i in range(39, -1, -1):
    if X + (1 << i) > K: continue
    if B[i] < N - B[i]: X += 1 << i

  ans = 0
  for a in A:
    ans += a ^ X

  return ans

print(solve())
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
answer = sorted(a)[1]
for b in range(answer):
    cnt = 2
    flag = True
    for i in range(n):
        if a[i] % answer != 0:
            cnt -= 1
        if cnt == 0:
            flag = False
    if flag:
        break
    answer -= 1
print(answer)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
answer = sorted(a)[1]
if n == 2:
    pass
else:
    for b in reversed(range(answer)):
        cnt = 2
        flag = True
        for i in range(n):
            if a[i] % answer != 0:
                cnt -= 1
            if cnt == 0:
                flag = False
                break
        if flag:
            break
        answer -= 1
print(answer)
### BUGGY CODE ###

n = int(input())
count = 0
l = []
for i in range(n):
    a = ''.join(sorted(input()))
    count += l.count(a)
    l.append(a)
print(count)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = [""]*n
for i in range(n):
    a[i] = ''.join(sorted(input()))
b = list(Counter(a).values())
print(sum(int((i-1)*i/2) for i in b))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Apr  5 17:16:14 2019

@author: adachi-lab
"""

input_1 = input()
S = input()
l = []
r = []


N = input_1.split()[0]
Q = input_1.split()[1]

for i in range(int(Q)):
    input_3 = input()
    l.append(int(input_3.split()[0]))
    r.append(int(input_3.split()[1]))

W = [(S[x-1:y]).count('AC') for (x, y) in zip(l, r)]

for i in range(len(W)):
    print(W[i])



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Apr  8 10:49:27 2019

@author: adachi-lab
"""


input_1 = input()
S = input()
l = []
r = []

N = input_1.split()[0]
Q = input_1.split()[1]

for i in range(int(Q)):
    input_3 = input()
    l.append(int(input_3.split()[0]))
    r.append(int(input_3.split()[1]))
    
s_1 = []
x = 0
for w in range(len(S)-1):
    if S[w] == 'A' and S[w+1] == 'C':
        x += 1
        s_1.append(x)
    else:
        s_1.append(x)
        
s_1.insert(0,0)
w = []

for j in range(len(l)):
    p = s_1[r[j]-1]-s_1[l[j]-1]
    w.append(p)
    
for t in range(len(w)):
    print(w[t])
### BUGGY CODE ###

#c
n,k = map(int,input().split())
a = list(map(int,input().split()))
mul1 = 1
cnt = 0
for i in range(n-k+1):
    mul2 = 1
    for j in range(i,i+k):
        mul2 *= a[j]
    if cnt !=0:
        if mul2 >mul1:
            print("Yes")
        else:
            print("No")
    mul1 = mul2
    cnt+=1

### FIXED CODE ###

#c
n,k = map(int,input().split())
a = list(map(int,input().split()))

for i in range(n-k):
    if a[i]<a[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
N = int(input())
N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

S = input().rstrip()

counter = 0
for l_index in range(len(S) - 4):
    atama = int(S[l_index:l_index+2])
    if atama % 2 != 0:
        continue
    else:
        r_index = 4
        while True:
            saigo = l_index + r_index
            if saigo > len(S):
                break
            kouho = int(S[l_index:saigo])
            if kouho % 2019 == 0:
                counter += 1
            r_index += 1


print(counter)


# def main():

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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 2019

"""
gcd(10, 2019) = 1 互いに素
-> 10のmod2019での逆元(1/10)が存在
"""
S = input().rstrip()
s_list = list(map(int, list(S)))[::-1]

counts = [0] * MOD
counts[0] = 1

num, d = 0, 1

for s_element in s_list:
    num += s_element * d
    num %= MOD
    d *= 10
    d %= MOD
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

# ABC141 D -Powerful Discount Tickets

import numpy

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

str_A = input().split()
int_A = [int(n) for n in str_A]

for i in range(M):
    int_A[numpy.argmax(int_A)] = max(int_A)//2

print(sum(int_A))

### FIXED CODE ###

# ABC141 D -Powerful Discount Tickets

import heapq
import math

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

A = [-int(n) for n in input().split()]

heapq.heapify(A)


for i in range(M):
    heapq.heappush(A, math.ceil(heapq.heappop(A)/2))

print(-sum(A))
### BUGGY CODE ###

def d_two_sequences(N, A, B):
    from bisect import bisect_left, bisect_right
    ans = 0
    for k in range(28):
        T = 2**k
        b = sorted([i % (2 * T) for i in B])
        tmp = 0
        for a in [i % (2 * T) for i in A]:
            idx1 = bisect_left(b, T - a)
            idx2 = bisect_right(b, 2 * T - a - 1)
            idx3 = bisect_left(b, 3 * T - a)
            tmp += len(b[idx1:idx2]) + len(b[idx3:])
        if tmp & 1 == 1:
            ans += T
    return ans

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
print(d_two_sequences(N, A, B))

### FIXED CODE ###

def d_two_sequences():
    # 参考: https://atcoder.jp/contests/abc091/submissions/6048882
    import numpy as np
    N = int(input())
    A = np.array(input().split(), dtype=np.int32)
    B = np.array(input().split(), dtype=np.int32)

    bit = 1 << 28  # 入力は 28bit 未満の非負整数
    ans = 0
    while bit:
        # bit + 1 番目以上のビットは考慮する必要がないため、mask で除いてしまう
        mask = 2 * bit - 1
        A &= mask
        B &= mask
        A.sort()
        B.sort()

        # numpy.searchsorted() は bisect.bisect_left() と同等
        x1, x2, x3 = (np.searchsorted(B, v - A).sum() for v in [bit, 2 * bit, 3 * bit])
        # [0, x1 - 1], [x2, x3 - 1] 番目の要素は、bit 番目のビットが 0 である
        # [x1, x2 - 1], [x3, N - 1] 番目の要素は、bit 番目のビットが 1 である
        zero_cnt = x1 + (x3 - x2)
        if (N - zero_cnt) % 2:
            ans += bit  # 解の bit 番目のビットは 1 である
        bit >>= 1  # 下位ビットへ
    return ans

print(d_two_sequences())
### BUGGY CODE ###

import numpy as np
from collections import deque
import sys
input = sys.stdin.readline

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

ans = 0

d = ([0, 1], [0, -1], [1, 0], [-1, 0])


def bfs(x, y):
    m = np.full((H, W), -1, dtype=np.int)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if maximus < v+1:
                    maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
L = []
for i in range(N):
  a, b = [int(j) for j in input().split()]
  l = [a]*b
  L.extend(l)
L.sort()
print(L[K-1])

### FIXED CODE ###

N, K = [int(i) for i in input().split()]
L = []
for i in range(N):
  a, b = [int(j) for j in input().split()]
  L.append([a, b])
L.sort(key=lambda x: x[0])
#print(L)

cnt = 0
for x, y in L:
  cnt += y
  if cnt >= K:
    ans = x
    break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for i in range(M):
    bc = list(map(int, input().split()))
    BC.append(bc)

# A.sort()


for b, c in BC:
    A = A + [c] * b

A.sort(reverse=True)
ans = sum(A[:N])
print(ans)

### FIXED CODE ###

from operator import itemgetter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []
    for i in range(M):
        bc = list(map(int, input().split()))
        BC.append(bc)

    BC.sort(key=itemgetter(1), reverse=True)
    # B = []
    # for b, c in BC:
    #     B = B + [c] * b
    #     if len(B) > N:
    #         break

    A.sort(reverse=True)
    
    i = 0
    j = 0
    r = []

    cnt = 0
    while len(r) != N:
        # print(i, j)
        if j > M - 1:
            r.append(A[i])
            i += 1
            continue

        b, c = BC[j]
        if A[i] >= c:
            r.append(A[i])
            i += 1
        else:
            r.append(c)
            cnt += 1
            if cnt == b:
                j += 1
                cnt = 0

    # print(r)
    ans = sum(r)
    print(ans)


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

R, G, B, N = map(int, input().split())
color = [R, G, B]
color.sort(reverse = True)
maxr = N // color[0]
maxg = N // color[1]
count = 0
for i in range(maxr+1):
    for j in range(maxg+1):
        nokori = N - i * color[0] - j * color[1]
        amari = nokori % color[2]
        if nokori >= 0 and amari == 0:
            count += 1
print(count)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
color = [R, G, B]
color.sort(reverse = True)
maxr = N // color[0]
count = 0
for i in range(maxr+1):
    nokori = N - i * color[0]
    maxg = nokori // color[1]
    for j in range(maxg+1):
        nokorinow = nokori - j * color[1]
        amari = nokorinow % color[2]
        if amari == 0:
            count += 1

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


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


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

A.sort(reverse=True)

ans = 0

for _ in range(N):
    A.pop(0)
    A.pop()

    ans += A[0]
    A.pop(0)
    
print(ans)

### FIXED CODE ###

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

A.sort()
ans = 0

for i in range(N, 3*N, 2):
    ans += A[i]
    
print(ans)
### BUGGY CODE ###

N, Q = [int(s) for s in input().split(' ')]

S = input()
d = [0] * (len(S) + 1)
for i in range(1, len(S) + 1):
    l, r = 1, i
    s = S[l - 1:r]
    d[r] = len(('x' + s + 'x').split('AC')) - 1

for q in range(Q):
    l, r = [int(s) for s in input().split(' ')]
    dl = d[l]
    dr = d[r]
    print(dr - dl)


### FIXED CODE ###

N, Q = [int(s) for s in input().split(' ')]

S = input()
a = [0] * (len(S) + 1)
c = [0] * (len(S) + 1)
ac = [0] * (len(S) + 1)
for i in range(1, len(S) + 1):
    ac[i] = ac[i - 1]
    s = S[i - 1]
    if s == 'A':
        a[i] = 1
    if s == 'C':
        c[i] = 1
        if i > 1 and a[i - 1] == 1:
            ac[i] += 1
    
for q in range(Q):
    l, r = [int(s) for s in input().split(' ')]
    dl = ac[l]
    dr = ac[r]
    print(dr - dl)