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

from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
S_T = [[int(s[w]) for s in S] for w in range(W)]
sumS = sum(map(sum, S_T))
ans = (H - 1) * (W - 1)

if sumS <= K:
    print(0)
else:
    for i in product([True, False], repeat=H-1):
        cnt = sum(i)
        M = [[0]]
        for j, k in enumerate(i):
            if k:
                M.append([])
            M[-1].append(j+1)
        A = [0] * len(M)
        for s_t in S_T:
            for l, m in enumerate(M):
                A[l] += sum(s_t[i] for i in m)
            if any(a > K for a in A):
                cnt += 1
                A = [sum(s_t[i] for i in m) for m in M]
                if any(a > K for a in A):
                    cnt = ans + 1
        ans = min(cnt, ans)
    print(ans)


### FIXED CODE ###

from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
S_T = [[int(s[w]) for s in S] for w in range(W)]
sumS = sum(map(sum, S_T))
ans = (H - 1) * (W - 1)

if sumS <= K:
    print(0)
else:
    for i in product([True, False], repeat=H-1):
        cnt = sum(i)
        if cnt >= ans:
            continue
        M = [[0]]
        for j, k in enumerate(i):
            if k:
                M.append([])
            M[-1].append(j+1)
        A = [0] * len(M)
        for s_t in S_T:
            for l, m in enumerate(M):
                A[l] += sum(s_t[i] for i in m)
            if any(a > K for a in A):
                cnt += 1
                if cnt >= ans:
                    break
                A = [sum(s_t[i] for i in m) for m in M]
                if any(a > K for a in A):
                    cnt = ans + 1
                    break
        ans = min(cnt, ans)
    print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate
def input(): return sys.stdin.readline().rstrip()

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

    for _ in range(K):
        new_A = [0] * (N)
        for i, a in enumerate(A):
            s = i - a
            if s < 0:
                s = 0
            f = i + a + 1
            new_A[s] += 1
            if f < N:
                new_A[f] -= 1
        A = list(accumulate(new_A))
    print(*A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate
def input(): return sys.stdin.readline().rstrip()

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

    for _ in range(K):
        new_A = [0] * (N)
        for i, a in enumerate(A):
            s = i - a
            if s < 0:
                s = 0
            f = i + a + 1
            new_A[s] += 1
            if f < N:
                new_A[f] -= 1
        A = list(accumulate(new_A))
        if min(A) == N:
            break
    print(*A)

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

# -*- coding: utf-8 -*-
"""
Created on Wed Jun 21 09:13:28 2017

@author: syaga
"""

COMMAND = ["insert", "delete", "deleteFirst", "deleteLast"]

if __name__ == "__main__":
    n = int(input())
    com = []
    for i in range(n):
        com.append(input().split())
    ans = []
    for i in com:
        if i[0] == COMMAND[0]:
            ans.append(i[1])
        elif i[0] == COMMAND[1]:
            if i[1] in ans:
                ind = len(ans)-1-ans[::-1].index(i[1])
                del ans[ind]
        elif i[0] == COMMAND[2]:
            ans.pop()
        elif i[0] == COMMAND[3]:
            ans.pop(0)
    ans.reverse()
    print(" ".join(ans))

### FIXED CODE ###

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

from collections import deque
import sys

COMMAND = ("insert", "delete", "deleteFirst", "deleteLast")

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    ans = deque()
    inp = sys.stdin.readlines()
    for i in range(n):
        com = inp[i].split()
        if com[0] == COMMAND[0]:
            ans.appendleft(com[1])
        elif com[0] == COMMAND[1]:
            if com[1] in ans:
                ans.remove(com[1])
        elif com[0] == COMMAND[2]:
            ans.popleft()
        elif com[0] == COMMAND[3]:
            ans.pop()
    print(" ".join(ans))
### BUGGY CODE ###

a, b, k = map(int,input().split())

for i in range(k):
  if a > 0:
    a = a - 1
  elif b > 0:
    b = b - 1

print(a, b)

### FIXED CODE ###

a, b, k = map(int,input().split())

if a >= k:
    a = a - k
else:
    b = b - k + a
    a = 0
    if b < 0:
        b = 0

print(a, b)
### BUGGY CODE ###

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

for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] == A[j]:
            print('NO')
            sys.exit()

print('YES')


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N-1):
    if A[i] == A[i+1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
import math

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

n=int(input())
s=input()
r=[]
r2=[]
g=[]
g2=[]
b=[]
b2=[]
for i in range(n):
  if s[i]=='R':
    r.append(i)
    r2.append(i*2)
  elif s[i]=='G':
    g.append(i)
    g2.append(i*2)
  else:
    b.append(i)
    b2.append(i*2)
ans=len(r)*len(g)*len(b)
for i in g:
  for j in b:
    if i+j in r2:
      ans-=1
for i in r:
  for j in b:
    if i+j in g2:
      ans-=1
for i in g:
  for j in r:
    if i+j in b2:
      ans-=1
print(ans)


### FIXED CODE ###

import bisect
n=int(input())
s=input()
r=[]
g=[]
b=[]
for i in range(n):
  if s[i]=='R':
    r.append(i)
  elif s[i]=='G':
    g.append(i)
  else:
    b.append(i)
ans=len(r)*len(g)*len(b)
r.append(n*4)
g.append(n*4)
b.append(n*4)
for i in g:
  for j in b:
    a=i+j
    if a%2==0 and r[bisect.bisect_left(r, a//2)]==a//2:
      ans-=1
for i in r:
  for j in b:
    a=i+j
    if a%2==0 and g[bisect.bisect_left(g, a//2)]==a//2:
      ans-=1
for i in g:
  for j in r:
    a=i+j
    if a%2==0 and b[bisect.bisect_left(b, a//2)]==a//2:
      ans-=1
print(ans+3)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
sum = 0

while k > 0:
    if a > 0:
        a -= 1
        sum += 1
    elif b > 0:
        b -= 1
    elif c > 0:
        c -= 1
        sum -= 1
    k -= 1

print(sum)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
sum = 0

if k >= a:
    sum += a
else:
    sum += k
    print(sum)
    exit()

k -= a+b
if k <= 0:
    print(sum)
    exit()

if k >= c:
    sum -= c
else:
    sum -= k

print(sum)
### BUGGY CODE ###

n, m = map(int, input().split())
list = [int(i) for i in input().split()]
for i in range(m):
  list[list.index(max(list))] = max(list)//2
 
print(sum(list))

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(n):
  a[i] *= -1

heapq.heapify(a)
for i in range(m):
    heapq.heapreplace(a, int(a[0] / 2))

print(sum(a)*-1)
### BUGGY CODE ###

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

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]

    INF = int(1e8)
    min_cost = [[INF] * W for i in range(H)]

    # q = []
    q = deque()
    for y in range(H):
        for x in range(W):
            if a[y][x] == "#":
                # heapq.heappush(q, (0, x, y))
                q.append((0, x, y))
    
    ans = 0
    while len(q) > 0:
        # cost, x, y = heapq.heappop(q)
        cost, x, y = q.popleft()
        # 最小コストでテーブルを更新
        if cost < min_cost[y][x]:
            ans = max(ans, cost)
            min_cost[y][x] = cost
            for nx, ny in [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if cost + 1 < min_cost[ny][nx]:
                        # heapq.heappush(q, (cost+1, nx, ny))
                        q.append((cost+1, nx, ny))
    
    print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())

    INF = int(1e7)
    a = np.array([list(map(lambda x: 0 if x=="#" else INF, list(input().strip()))) for i in range(H)])

    for i in range(H-1):
        a[i+1] = np.minimum(a[i] + 1, a[i+1])
    for i in range(H-1, 0, -1):
        a[i-1] = np.minimum(a[i] + 1, a[i-1])
    
    for i in range(W-1):
        a[:, i+1] = np.minimum(a[:, i] + 1, a[:, i+1])
    for i in range(W-1, 0, -1):
        a[:, i-1] = np.minimum(a[:, i] + 1, a[:, i-1])

    print(np.max(a))

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

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


for i in range (N):
    print(l.index(i + 1) + 1, end=" ")

### FIXED CODE ###

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

l_sorted = [0] * N

for i in range(N):
    l_sorted[l[i] - 1] = i + 1



for i in range (N):
    print(l_sorted[i])
### BUGGY CODE ###

def main():
    k,q = map(int, input().split())
    D=list(map(int, input().split()))
    for _ in range(q):
        n,x,m=map(int, input().split())
        mods=[d%m for d in D]
        S=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m
        ans=n-through-1
        ans-=mods.count(0)*((n-1)//k)+mods[:(n-1)%k].count(0)
        print(ans)
main()

### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)
### BUGGY CODE ###

S=input()
res=0
a=1
re=0
while a!=0:
  S=S.replace("10","3")
  S=S.replace("01","3")
  res+=S.count("3")*2
  S=S.replace("3","")
  a=re-res
  re=res
print(res)


### FIXED CODE ###

S=input()
if S.count("1")>=S.count("0"):
  print(S.count("0")*2)
else:
  print(S.count("1")*2)
### BUGGY CODE ###

N,M=map(int,input().split())
total=1
mod=1000000007
if N==M:
    for i in range(1,N+1):
        total=total*i*i
    print((total*2)%mod)

elif N+1==M or M+1==N:
    total*=max(M,N)
    for i in range(1,min(M,N)+1):
        total=total*i*i
    print(total%mod)
else:
    print(0)

### FIXED CODE ###

N,M=map(int,input().split())
total=1
mod=1000000007
if N==M:
    for i in range(1,N+1):
        total=total*i*i
        total=total%mod
    print((total*2)%mod)

elif N+1==M or M+1==N:
    total*=max(M,N)
    for i in range(1,min(M,N)+1):
        total=total*i*i
        total=total%mod
    print(total%mod)
else:
    print(0)
### BUGGY CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    INF = float('inf')
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    for i in range(N):
        if i == 0:
            dp[i] = 0
        for j in range(AB[i][0],H+maxA):
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ (b*i)%13 for i in range(10) ] )
#
dp= [ 0 for i in range(13) ]
dp[0] = 1
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    #
    if c=="?":
        bset = mmap[i%6][1:]
        for m in range(13):
            num= tmp[m]
            if num==0: continue
            for b in bset:
                idx= (m+b)%13
                dp[idx]= ( dp[idx] + num ) % MOD
    else:
        b= mmap[i%6][int(c)]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
#
print(dp[5])


### FIXED CODE ###

import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])
### BUGGY CODE ###

H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:    # 3の倍数だったら最小値は0
    print(0)
    exit()
answer = float('inf')
h = 1
for _ in range(((H-1)//2)+1):
    a = h * W
    w = 1
    for _ in range(((W-1)//2)+1):
        b = (H-h) * w
        c = H * W - a - b
        MAX = max([a, b, c])
        MIN = min([a, b, c])
        if MAX - MIN <= answer:
            answer = MAX - MIN
        w += 1
    h += 1

w = 1
for _ in range(((W-1)//2)+1):
    a = w * H
    h = 1
    for _ in range(((H-1)//2)+1):
        b = (W-w) * h
        c = H * W - a - b
        MAX = max([a, b, c])
        MIN = min([a, b, c])
        if MAX - MIN <= answer:
            answer = MAX - MIN
        h += 1
    w += 1

print(answer)

### FIXED CODE ###

H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:    # 3の倍数だったら最小値は0
    print(0)
    exit()

answer = float('inf')

h = 1
for _ in range(H):
    a = h * W
    b = (H-h) * (W // 2)
    c = H * W - a - b
    MAX = max([a, b, c])
    MIN = min([a, b, c])
    if MAX - MIN <= answer:
        answer = MAX - MIN
    h += 1

w = 1
for _ in range(W):
    a = w * H
    b = (W-w) * (H // 2)
    c = H * W - a - b
    MAX = max([a, b, c])
    MIN = min([a, b, c])
    if MAX - MIN <= answer:
        answer = MAX - MIN
    w += 1

a = W // 3
b = (W - a) // 2
c = W - a - ((W - a) // 2)
a *= H
b *= H
c *= H
MAX = max([a, b, c])
MIN = min([a, b, c])
if MAX - MIN <= answer:
    answer = MAX - MIN

a = H // 3
b = (H - a) // 2
c = H - a - ((H - a) // 2)
a *= W
b *= W
c *= W
MAX = max([a, b, c])
MIN = min([a, b, c])
if MAX - MIN <= answer:
    answer = MAX - MIN

print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [None] * N

def solve(idx):
    if dp[idx] is not None:
        return dp[idx]

    if idx == N - 1:
        dp[idx] = 0
    elif idx == N - 2:
        dp[idx] = abs(h[idx] - h[idx + 1])
    else:
        temp = 10**10
        for k in range(1, K + 1):
            if idx + k == N:
                break
            temp = min(temp, solve(idx + k) + abs(h[idx] - h[idx + k]))
        dp[idx] = temp
    return dp[idx]

print(solve(0))


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

#print(dp)
print(dp[n-1])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
from bisect import bisect_left as bl,bisect_right as br
for i in range(n):
    for j in range(i+1,n):
        a,s=l[i],l[j]
        ans+=-1-int(s<2*a)+bl(l,a+s)-br(l,s-a)
print(ans//3)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
from bisect import bisect_left as bl,bisect_right as br
for i in range(n):
    for j in range(i+1,n):
        a,s=l[i],l[j]
        ans+=-1-int(s<2*a)+bl(l,a+s)-br(l,s-a)
print(ans//3)
### BUGGY CODE ###

#!/usr/bin/python3

n, c = map(int, input().split())
x = [0]
v = [0]
ca = [0]
csum = 0
for i in range(n):
    xi, vi = map(int, input().split())
    x.append(xi)
    v.append(vi)
    csum += vi
    ca.append(csum)
x.append(c)

cb = [0]
for i in range(n):
    csum -= v[i]
    cb.append(csum)
cb.append(0)

gainMax = 0
for a in range(n + 1):
    for b in range(a + 1, n + 2):
        gain = ca[a] + cb[b]
        loss1 = x[a] * 2 + (c - x[b])
        loss2 = x[a] + (c - x[b]) * 2
        loss = min(loss1, loss2)
        gainMax = max(gainMax, gain - loss)

print(gainMax)

### FIXED CODE ###

#!/usr/bin/python3

n, c = map(int, input().split())
x = [0]
v = [0]
ca = [0]
csum = 0
dmaxa1 = [0]
dmaxa2 = [0]
dmaxa1i = 0
dmaxa2i = 0
for i in range(n):
    xi, vi = map(int, input().split())
    x.append(xi)
    v.append(vi)
    csum += vi
    ca.append(csum)
    dmaxa1i = max(dmaxa1i, csum - xi)
    dmaxa2i = max(dmaxa2i, csum - xi * 2)
    dmaxa1.append(dmaxa1i)
    dmaxa2.append(dmaxa2i)
x.append(c)

cb = [0]
for i in range(n):
    csum -= v[i]
    cb.append(csum)
cb.append(0)

gainMax = 0
for b in range(1, n + 2):
    gain = cb[b]
    loss1 = (c - x[b]) * 2
    loss2 = c - x[b]
    d1 = dmaxa1[b - 1] + gain - loss1
    d2 = dmaxa2[b - 1] + gain - loss2
    gainMax = max(gainMax, max(d1, d2))

print(gainMax)
### BUGGY CODE ###

#coding: UTF-8
import math
N = int(input())
#print(N)



for i in range(1,N+1):
  if i <=5:
    print(0)
    continue
  cnt = 0
  m = int(math.sqrt(i))
  #平方根までやればよい
  for x in range(1,m):
    for y in range(x,m):
      for z in range(y,m):
        a = (x+y+z)**2 -x*y -y*z - z*x
        if a == i:
          if x==y==z:
            cnt += 1
          elif x==y or y==z:
            cnt += 3
          else:
            cnt += 6
  print(cnt)

### FIXED CODE ###

#coding: UTF-8
import math
N = int(input())
#print(N)

ans = [0]*10001

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      a = x**2+y**2+z**2+x*y+y*z+z*x
      if a <=10000:
        ans[a] += 1
    
for i in range(1,N+1):
  print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
 
 
def solve(N: int, A: "List[int]"):
 
    a = [-INF]
 
    def isOK(index, key):
        return a[index] < key
 
    def binary_search(key):
        ng = -1
        ok = len(a)
 
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok
 
    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return
 
 
def main():
 
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


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

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

for _  in range(Q):
  l, r = map(int,input().split())
  x = S[l-1:r]
  print(x.count("AC"))

### FIXED CODE ###

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

import sys
import math
readline = sys.stdin.readline


def main():
    k = int(readline().rstrip())
    kSum = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                kSum += gcd(a, b, c)
    print(kSum)


def gcd(a, b, c):
    return math.gcd(math.gcd(a, b), c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import time
readline = sys.stdin.readline


def main():
    listSum = [1, 3, 6]
    k = int(input())
    sumGCD = 0
    for a in range(1, k + 1):
        for b in range(a, k + 1):
            for c in range(b, k + 1):
                sumGCD += gcd(a, b, c) * listSum[len(set([a, b, c])) - 1]
    print(sumGCD)


def gcd(a, b, c):
    return math.gcd(math.gcd(a, b), c)


if __name__ == '__main__':
    s = time.time()
    main()
    # print(time.time() - s)
### BUGGY CODE ###

N = int(input())
def judge(x):
    for i in range(4):
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
        if ''.join(x).count('AGC') >= 1:
            return False
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
    return True
LI = ['A','G','C','T']
def dp(n,p,q,r):
    if n == 3:
        if [p,q,r] == ['A','G','C']:
            return 0
        elif [p,q,r] == ['A','C','G']:
            return 0
        elif [p,q,r] == ['G','A','C']:
            return 0
        else:
            return 1
    else:
        cnt = 0
        for l in LI:
            if judge([l,p,q,r]):
                cnt += dp(n-1,l,p,q)
        return cnt
ans = 0
for i in LI:
    for j in LI:
        for k in LI:
            ans += dp(N,i,j,k)
print(ans)

### FIXED CODE ###

N = int(input())
mod = 10**9 +7
stack = [[0 for _ in range(64)] for _ in range(N+1)]
LI = ['0','1','2','3']
def judge(x):
    for i in range(4):
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
        if ''.join(x).count('012') >= 1:
            return False
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
    return True
def nu(x,y,z):
    return 16*int(x)+4*int(y)+int(z)
for i in range(64):
    if (i == 6) or (i == 9) or (i == 18):
        stack[3][i] = 0
    else:
        stack[3][i] = 1
for i in range(4,N+1):
    for j in LI:
        for k in LI:
            for l in LI:
                cnt = 0
                for m in LI:
                    if judge([m,j,k,l]):
                        cnt += stack[i-1][nu(m,j,k)] 
                stack[i][nu(j,k,l)] = cnt % mod
ans = 0
for i in range(64):
    ans += stack[N][i]
print(ans % mod)