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

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

for i in range(q):
    li, ri = map(int, input().split())
    tmp = s[li-1:ri]
    count = 0
    for j in range(len(tmp)-1):
        if tmp[j] == 'A' and tmp[j+1] == 'C':
            count += 1
    print(count)

### FIXED CODE ###

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

l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

acs = [0]
count = 0
idx = 1
while True:
    if idx == n:
        break
    if s[idx-1] == 'A' and s[idx] == 'C':
        count += 1
    acs.append(count)
    idx += 1

for i in range(q):
    print(acs[r[i]-1] - acs[l[i]-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: int, B: int):
    if A > B:
        tmp = A
        A = B
        B = A
    
    count = 0
    while True:
        if (B - A) % 2 == 0:
            count += (B - A) // 2
            break
        else:
            if max(A-1, B-1) < max(N-A, N-B):
                A = max(1, A-1)
                B -= 1
                count += 1
            else:
                A += 1
                B = min(N, B+1)
                count += 1
    print(count)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))  # type: int
    B = int(next(tokens))  # type: int
    solve(N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: int, B: int):
    if A > B:
        tmp = A
        A = B
        B = tmp
    
    count = 0
    while True:
        if (B - A) % 2 == 0:
            count += (B - A) // 2
            break
        elif A != 1 and B != N:
            if A-1 < N-B:
                count += A-1
                B = B - (A-1)
                A = 1


            else:
                count += N-B
                A = A + (N-B)
                B = N
        else:
            if A == 1:
                count += 1
                B -= 1
                
            elif B == N:
                count += 1
                A += 1
    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))  # type: int
    B = int(next(tokens))  # type: int
    solve(N, A, B)

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


from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs(i):
    #if i not in bgraph[j]:
    #    seen[i]= True
    #else:
    #    seen[i]="block"
    #if graph[i]:
    #    for nec in graph[i]:
    #        if seen[nec] == False:
    #            dfs(nec,j)
    seen[i] = True
    que = deque([i])
    while que:

        neci = que.pop()
        for nec in graph[neci]:
            if seen[nec]== False:
                if nec not in bgraph[i]:
                    seen[nec]=True
                else:
                    seen[nec]="block"
                que.append(nec)

for i_n in range(N):
    seen = [False for _ in range(N)]
    dfs(i_n)
    #print(seen)
    cnt.append(seen.count(True) - 1 - len(graph[i_n]))

print(*cnt)


### FIXED CODE ###

#計算時間が足りない　何がダメなのか　工夫が足りない　研究が必要
from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = [0]*N
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]
seenb = [False for _ in range(N)]
def dfs():
    labelb = 1
    #while False in seen:
    for i in range(N):
        if seen[i] != False: continue
        label = 1
        #i = seen.index(False)
        seen[i] = label
        seenb[i] = labelb
        que = deque([i])
        seg = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    seenb[nec]=labelb
                    que.append(nec)
                    seg.append(nec)
                    label += 1
        for iii in seg:
            seen[iii] = label

        labelb += 1

dfs()
for i in range(N):
    count = seen[i] - 1 -len(graph[i])
    if bgraph[i] and seen[i]>=2:
          for j in bgraph[i]:
                if seenb[i] == seenb[j]:
                    count -= 1
    cnt[i]=count
print(*cnt)
### BUGGY CODE ###

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10000;t=[0]*10000
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(int,sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans


### FIXED CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans
### BUGGY CODE ###

N=raw_input()
LN=raw_input().split()

n = int(N)
ln = [int(i) for i in LN]

ln.sort()

r = []
for i in range(n-1, -1, -1):
    a = ln[i]
    for j in range(i-1, -1, -1):
        b = ln[j]
        if a > 2*b:
            break
        for k in range(j-1, -1, -1):
            # always, a > b > c
            c = ln[k]
            if not a < b + c:
                break
            #if not b < c + a:
            #    break
            #if not c < a + b:
            #    continue
            r.append([a,b,c])

print len(r)

### FIXED CODE ###

import bisect

N=int(raw_input())
LN=map(int, raw_input().split())

LN.sort()

r = 0
for i in xrange(N-1, 1, -1):
    a = LN[i]
    for j in xrange(i-1, 0, -1):
        b = LN[j]
        if a > 2*b:
            break
        idx = bisect.bisect_left(LN, a-b+1)
        if idx < j:
            r += j - idx

print r
### BUGGY CODE ###

N = int(input())
S_row = [input() for _ in range(N)]

S = list(filter(lambda n: n[0] in "MARCH", S_row))

ans = 0
for i, s1 in enumerate(S):
    for j, s2 in enumerate(S[i+1:]):
        if s2[0] != s1[0]:
            for s3 in S[i+j+1:]:
                if s3[0] != s1[0] and s3[0] != s2[0]:
                    ans += 1
print(ans)


### FIXED CODE ###

from itertools import combinations
from functools import reduce
from operator import mul

N = int(input())
S_row = [input() for _ in range(N)]

count = [0] * 5
for i, c in enumerate("MARCH"):
    count[i] = len(list(filter(lambda n: n[0] == c, S_row)))

print(sum(map(lambda x: reduce(mul, x), combinations(count, 3))))
### BUGGY CODE ###

#import math
#import sys
#import bisect
#input = sys.stdin.readline
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))

def main():
    #x,y = map(int,input().split())	x=1,y=2
    #a = input().split()	a=['1','2','3',...,'n']
    #a = list(map(int,input().split()))	a=[1,2,3,4,5,...,n]
    #li = input().split('T')	FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    n=int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        x=[]
        for j in range(n):
            if i!=j:
                x.append(a[j])
        x.sort()
        y=len(x)
        if len(x)%2==1:
            print(x[((y+1)//2)-1])
        else:
            print((x[y//2]+x[(y//2)-1])/2)
main()

### FIXED CODE ###

import math
import copy
#import sys
#import bisect
#input = sys.stdin.readline
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))

def main():
    #x,y = map(int,input().split())	x=1,y=2
    #a = input().split()	a=['1','2','3',...,'n']
    #a = list(map(int,input().split()))	a=[1,2,3,4,5,...,n]
    #li = input().split('T')	FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    n=int(input())
    a = list(map(int,input().split()))
    b=copy.copy(a)
    a.sort()
    for i in range(n):
        x=b[i]
        if x<=a[(n//2)-1]:
            print(a[(n//2)])
        else:
            print(a[(n//2)-1])

main()
### BUGGY CODE ###

import math

r = 999999
sqrt = int(math.sqrt(r))
p = [1 for i in range(r)]
p[0] = 0
for i in p[:sqrt]:
    if i:
        for j in range(2*(i+1)-1,r,i+1):
            p[j] = 0

while True:
    try:
        n = int(raw_input())
        print sum(p[:n])
    except:
        break

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
### BUGGY CODE ###

N,X = map(int,input().split())
positions_from_X = [abs(int(x)-X) for x in input().split()]

min_distance = min(positions_from_X)

n = min_distance

for d in sorted([i for i in range(1,n+1) if n%i==0], reverse=True):
    flg = d
    for p in positions_from_X:
        if p%d !=0:
            flg=0
            break
    if flg:
        break

print(flg)

### FIXED CODE ###

N,X = map(int,input().split())
positions_from_X = [abs(int(x)-X) for x in input().split()]

n = min(positions_from_X)

if N==1:
    flg = n
else:
    for d in sorted([i for i in range(1,n+1) if n%i==0], reverse=True):
        flg = d
        for p in positions_from_X:
            if p%d !=0:
                flg=0
                break
        if flg:
            break

print(flg)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    b=int(input())
    if b in a:
        a.remove(b)
    else:
        a.append(b)
print(len(a)) 

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
h=a[0]
ans=1
for i in a[1:]:
    if i!=h:
        ans+=1
        h=i
    else:
        ans-=1
        h=pow(10,10)    
print(ans)
### BUGGY CODE ###

word = input()


#%%
# word = "BBBWWW"


#%%
ans = 0
for i in range(len(word)):
    if word[i] == "B":

        ans += len(word[i+1:].replace("B",""))
    
print(ans)
#%%


#%%


### FIXED CODE ###

word = input()


#%%
# word = "BWBWBW"


#%%
word.count("W")
#%%
ans = 0
to_plus = word.count("W")
for i in range(len(word)):
    if word[i] == "B":
        ans += to_plus
    else:
        to_plus -= 1

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

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
    l = []
    ans = 0
    for sy, sx in S:
      for gy, gx in G:
        if sy == gy and sx == gx:
          continue
        maze1 = copy.deepcopy(maze)
        maze1[sy][sx]=0
        que=deque([[sy,sx]])
        while que:
          y,x=que.popleft()
          for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!='#':
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                if nexty == gy and nextx == gx:
                  break
                que.append([nexty,nextx])
        ans = max(ans, maze1[gy][gx])
    print(ans)
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    last_div = 0
    while c < w:# 左から貪欲
        r_idx = 0
        
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 1行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if c == last_div:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize",last_div)
        c += 1
    ans = min(ans,ans_i)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
n=int(input())
col=[{}for i in range(n)]
edges=[set() for i in range(n)]
ed=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].add(s-1);edges[s-1].add(a-1)
    ed.append((a-1,s-1))
m=0
ind=-1
for i in range(n):
    if m<len(edges[i]):
        ind=i
        m=len(edges[i])
print(m)
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i,e in zip(range(1,m+1),edges[ind]):
    col[e][ind]=i
    dq.append(e)
x=set(range(1,m+1))
while dq:
    a=dq.popleft()
    c=x-set(col[a].values())
    for to in edges[a]-set(col[a].keys()):
        col[to][a]=c.pop()
        dq.append(to)
for i,j in ed:
    if j in col[i]:
        print(col[i][j])
    else:
        print(col[j][i])


### FIXED CODE ###

n=int(input())
edges=[[] for i in range(1+n)]
e={}
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    e[(_,__)]=i
    e[(__,_)]=i
    """
"""#weighted->erase
f=max(len(j)for j in edges)
print(f)
ret=[0]*(n-1)
from collections import deque
dq=deque([(1,1)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
while dq:
    a,c=dq.popleft()
    for to in edges[a]:
        if ret[e[(a,to)]]:continue
        ret[e[(a,to)]]=c
        c=c%f+1
        dq.append((to,c))
        
print(*ret,sep="\n")
### BUGGY CODE ###

from functools import reduce

INF = float("inf")

N, a, b, *A = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

def solve(a, b, c):
    if (a % 2) ^ (b % 2) != (c % 2):
        return INF
    if c == 0:
        return INF if a < b else (a - b) // 2

    return min(
        2 * solve(a // 2, b // 2, c // 2),
        1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2)
    )

print(-1 if (res := solve(a, b, c)) >= a else res)

### FIXED CODE ###

from functools import reduce, lru_cache

INF = float("inf")

N, a, b, *A = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

@lru_cache(None)
def solve(a, b, c):
    if (a % 2) ^ (b % 2) != (c % 2):
        return INF
    if c == 0:
        return INF if a < b else (a - b) // 2

    return min(
        2 * solve(a // 2, b // 2, c // 2),
        1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2)
    )

print(-1 if (res := solve(a, b, c)) >= a else res)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
    Y = [0]*(n+1)
    for i, x in enumerate(a):
        Y[max(0, i-x)] += 1
        Y[min(n, i+x+1)] -= 1
    for j in range(1, n):
        Y[j] += Y[j-1]
    if a == Y[:-1]:
        break
    a = Y[:-1]
print(*a)

### FIXED CODE ###

from numba import jit
N, K = map(int, input().split())
A = list(map(int, input().split()))

@jit
def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

ans=solve(K,N,A)
print(*ans)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import deque
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    S = deque(S)
    for i in range(N):
        lp[int(''.join(S))%P] += 1
        S.popleft()
    ans = lp[0]
    for i in range(P):
        ans += max(lp[i]*(lp[i]-1)//2, 0)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

N,X,Y = map(int,input().split())
for k in range(1,N):
    S = 0
    for i in range(1,N):
        for j in range(i+1,N+1):
            if min(j-i,abs(X-i)+abs(Y-j)+1) == k:
                S += 1
    print(S)

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

import math

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

for i in range(M):
    j = max(enumerate(a), key=lambda x: x[1])[0]
    a[j] /= 2
for i in range(N):
    a[i] = math.floor(a[i])
print(sum(a))


### FIXED CODE ###

import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))
### BUGGY CODE ###

#import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

#dp = np.zeros((n+1, w+1), np.int64)
dp = [[0] * (w+1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            #dp[i+1][sum_w] = max(dp[i][sum_w - wi] + vi, dp[i+1][sum_w])
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])

print(dp[n][w])

### FIXED CODE ###

import numpy as np

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, w+1), np.int64)

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.maximum(dp[i][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
"""
for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])
"""
#print(dp)
print(dp[n][w])