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

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

#Sum = np.zeros(N)
#
#for i in range(N):
#    Sum[i] = Sum[i-1] + A[i]

count = 0



for i in range(N):
    S = 0
    S = A[i]
    if S == 0:
        count += 1
    for j in range(i+1, N):
        S += A[j]
        if S == 0:
            count += 1
            
print(count)

### FIXED CODE ###

import math

N = int(input())

a = list(map(int, input().split()))
b = [a[0] for i in range(N)]

for i in range(1, N):
    b[i] = b[i-1] + a[i]
    
b.sort()
c = 1
ans = 0

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)   

def C(n, r):
    return P(n, r)//math.factorial(r)

if N==1:
    if b[0]==0:
        print(1)
    else:
        print(0)
else:
    for i in range(1, N):
        if b[i]==b[i-1]:
            c = c+1
        else:
            if c>1:
                ans = ans + C(c, 2)
            if b[i-1]==0:
                ans = ans + c
            c=1
    else:
        if c>1:
            ans = ans + C(c, 2)
        if b[i-1]==0:
            ans = ans + c
    
    print(ans)
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = floyd_warshall(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


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

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(m):
    data = list(map(int,input().split()))
    l.append(data)
l.sort(key=lambda x:x[1])

import heapq
heapq.heapify(a)

for tmp in l:
    b=tmp[0]
    c=tmp[1]

    for i in range(b):
        heapq.heappushpop(a,c)

print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(m):
    data = list(map(int,input().split()))
    l.append(data)
l.sort(key=lambda x:x[1])
l.reverse()

a.sort()

b_idx=0
nokori=l[b_idx][0]
for i in range(n):
    if a[i] > l[b_idx][1]:
        break
    else:
        a[i] = l[b_idx][1]
        nokori-=1
        if nokori == 0:
            b_idx+=1
            if b_idx >= m:
                break
            nokori=l[b_idx][0]

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

import sys
input=sys.stdin.readline
n,a,b,c=map(int,input().split())
s=[input() for i in range(n)]
dp=[dict() for i in range(n+1)]
dp[0][(a,b,c)]=""
for i in range(n):
    if len(dp[i])==0:
        print("No")
        break
    if s[i][0]=="A" and s[i][1]=="B":
        #print(0)
        for j in dp[i]:
            a,b,c=j
            if a>0:
                dp[i+1][(a-1,b+1,c)]=dp[i][j]+"B"
            if b>0:
                dp[i+1][(a+1,b-1,c)]=dp[i][j]+"A"
    elif s[i][0]=="A" and s[i][1]=="C":
        #print(1)
        for j in dp[i]:
            a,b,c=j
            if a>0:
                dp[i+1][(a-1,b,c+1)]=dp[i][j]+"C"
            if c>0:
                dp[i+1][(a+1,b,c-1)]=dp[i][j]+"A"
    else:
        #print(2)
        for j in dp[i]:
            a,b,c=j
            if b>0:
                dp[i+1][(a,b-1,c+1)]=dp[i][j]+"C"
            if c>0:
                dp[i+1][(a,b+1,c-1)]=dp[i][j]+"B"
else:
    if len(dp[n])==0:
        print("No")
    else:
        print("Yes")
        #print(dp)
        z=list(dp[n].items())
        #print(z)
        for i in range(n):
            print(z[0][1][i])






### FIXED CODE ###

n,a,b,c=map(int,input().split())
s_=[input() for i in range(n)]
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if a==1 and b==1 and i!=n-1:
            if s_[i+1][0]=="A":
                a,b,ans=(a+1,b-1,ans+"A")
            else:
                a,b,ans=(a-1,b+1,ans+"B")
            continue
        a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if a==1 and c==1 and i!=n-1:
            if s_[i+1][1]=="C":
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a+1,c-1,ans+"A")
            continue
        a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if c==1 and b==1 and i!=n-1:
            if s_[i+1][1]=="C":
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b+1,c-1,ans+"B")
            continue
        b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])
### BUGGY CODE ###

n = int(input())
cnt = 1
for i in range(1, n+1):
  cnt *= i

r = cnt % (10**9 + 7)
print(r)
  

### FIXED CODE ###

import math
n = int(input())
print(math.factorial(n) % (10**9 + 7))
### BUGGY CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ans = 0
hq = []
for i in range(1, m+1):
    for a, b in ab:
        if a == i and not -b in hq:
            heappush(hq, (-b, a))
    
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort()
ans = 0
hq = []
idx = 0
for i in range(1, m+1):
    for j in range(idx, n):
        if ab[j][0] == i:
            heappush(hq, (-ab[j][1], ab[j][0]))
            idx += 1
        else:
            break
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import fractions
from functools import reduce

MOD = 1000000007  # type: int

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

def solve(N: int, A: "List[int]"):
    LCM = reduce(lcm,A)
    answer = 0
    for i in range(N):
        answer += LCM//A[i]
        answer %= MOD
    print(answer)
    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
import fractions
from functools import reduce
import random

MOD = 1000000007  # type: int

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

def solve(N: int, A: "List[int]"):

    LCM = reduce(lcm,A)
    answer = 0
    for i in range(N):
        answer += LCM//A[i]
    print(answer%MOD)
    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()
### BUGGY CODE ###

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

for i in range(M):
    x = max(a)
    a[a.index(x)]=x//2
print(sum(a))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
a = [-i for i in list(map(int,input().split()))]
heapq.heapify(a)
for i in range(M):
    m = heapq.heappop(a)
    heapq.heappush(a,-(-m//2))
print(-sum(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1
for _ in range(n-1):
    ll=[]
    for i in l:
        if i[1]>=l[0][0]:
            ll.append(i)
    l=ll
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
for i in start:
    if i in goal:
        ans = 'POSSIBLE'
print(ans)


### FIXED CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
for i in range(1,n+1):
  print(a.count(i))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
b= [0]*n
for i in a:
  b[i-1]+=1
for i in b:
  print(i)
### BUGGY CODE ###

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

ans=True
for i in range(n):
	for k in range(i+1,n):
		if a[i]==a[k]:
			ans=False

print("YES" if ans else "NO")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
setA=set(a)
print("YES" if len(setA)==n else "NO")
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline




#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    residual_flow = [[0] * v for _ in range(v)]
    g = defaultdict(list)
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            residual_flow[s][t] = c

    while True:
        route, flow = search(g, residual_flow, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual_flow[route[i - 1]][route[i]] -= flow
            residual_flow[route[i]][route[i - 1]] += flow

    print(sum(residual_flow[i][source] for i in g[source]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        if u in route:
            continue
        
        route.append(u)
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    g = defaultdict(set)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c and s != sink and t != source:
            g[s] |= {t}
            g[t] |= {s}
            residual[s][t] = c

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow

    print(sum(residual[sink][i] for i in g[sink]))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]

for i, x in enumerate(A):
    while x != 1:
        s[i].add(p[x])
        x //= p[x]

l = sum(len(x) for x in s)
merge = lambda x, y: x|y
print("pairwise coprime" if l == len(reduce(merge, s)) else "setwise coprime")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")
### BUGGY CODE ###

from sys import stdin

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def __iter__(self):
        self.it = self.head.next
        return self
    def __next__(self):
        if self.it == self.last:
            raise StopIteration
        k = self.it.key
        self.it = self.it.next
        return k

dlist = DList()

n = int(stdin.readline())
for i in range(n):
    cmd = tuple(stdin.readline().split())
    if   cmd[0] == 'insert':
        dlist.insert((cmd[1]))
    elif cmd[0] == 'delete':
        dlist.delete((cmd[1]))
    elif cmd[0] == 'deleteFirst':
        dlist.deleteFirst()
    elif cmd[0] == 'deleteLast':
        dlist.deleteLast()

print(' '.join((dlist)))


### FIXED CODE ###

from sys import stdin

class DList:
    class Cell:
        def __init__(self, k):
            self.key  = k
            self.prev = None
            self.next = None

    def __init__(self):
        self.head = DList.Cell(None)
        self.last = DList.Cell(None)
        self.head.next = self.last
        self.last.prev = self.head

    def insert(self, x):
        c = DList.Cell(x)
        c.prev = self.head
        c.next = self.head.next
        c.next.prev = c
        self.head.next = c

    def delete(self, x):
        c = self.__find(x)
        if c != None:
            self.__delete(c)

    def __delete(self, c):
        c.prev.next = c.next
        c.next.prev = c.prev

    def __find(self, x):
        c = self.head.next
        while c != None and c.key != x:
            c = c.next
        return c

    def deleteFirst(self):
        self.__delete(self.head.next)
    def deleteLast(self):
        self.__delete(self.last.prev)

    def __iter__(self):
        self.it = self.head.next
        return self
    def __next__(self):
        if self.it == self.last:
            raise StopIteration
        k = self.it.key
        self.it = self.it.next
        return k

dlist = DList()

n = int(stdin.readline())
for i in range(n):
    cmd = stdin.readline()
    if   cmd.startswith('insert'):
        dlist.insert(cmd[7:-1])
    elif cmd.startswith('deleteFirst'):
        dlist.deleteFirst()
    elif cmd.startswith('deleteLast'):
        dlist.deleteLast()
    elif cmd.startswith('delete'):
        dlist.delete(cmd[7:-1])

print(' '.join(dlist))
### BUGGY CODE ###

n=int(input())
s=input()
mx=0
for i in range(1,n):
  c=0
  for j in range(n-i):
    if s[j]==s[j+i]:
      c+=1
      mx=max(mx,c)
      if c==i:
        break
    else:
      c=0
print(mx)

### FIXED CODE ###

n=int(input())
s=input()
mx=0
for i in range(1,n):
  c=0
  for j in range(n-i):
    if s[j]==s[j+i]:
      c+=1
      mx=max(mx,c)
      if c==i:
        break
    else:
      c=0
print(mx)
### BUGGY CODE ###



N = int(input())
D = [int(input()) for i in range(N)]

e = [0 for j in range(N)]

for i in range(N):
    e = D[:]
    e[i] = 0
    print(max(e))
    

### FIXED CODE ###

N = int(input())
d = [int(input()) for i in range(N)]

M = max(d)
D = d[:]
d.remove(M)
m = max(d)

for j in range(N):
    if D[j]==M:
        print(m)
    else:
        print(M)
### BUGGY CODE ###


n =int(input())
s = list(map(int,input().split()))
k = 1
for _ in range(n):
  k *= s[_]

if len(str(k-1)) < 19:
  print(k)
else :
  print("-1")

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 1
if 0 in s:
  print(0)
  exit()
for _ in range(n):
  ans *= s[_]
  if ans > 10**18:
    print(-1)
    exit()
else:
  print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
un = []
ans = 0
for i, x in enumerate(p):
    un.append(x)
    if x <= min(un):
        ans += 1        
print(ans)


### FIXED CODE ###

n = int(input())
ps = list(map(int, input().split()))
m = ps[0]
ans = 0
for p in ps:
    m = min(p, m)
    if p <= m:
        ans += 1        
print(ans)
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]

    prime_list = primes(10**6)

    lcm_dic = {}
    Alist = []
    for a in A:
        a_dic = {}
        for num in prime_list:
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

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

A = [a for i, a in enumerate(A) if a <= i+1]
k = 0

while k < len(A):
    if A[k] != k+1:
        A.pop(k)
    else:
        k += 1

if len(A) == 0:
    print(-1)
else:
    print(N - len(A))

### FIXED CODE ###

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

A = [a for i, a in enumerate(A) if a <= i+1]

k = 0
for a in A:
    if a == k+1:
        k += 1
    

if k == 0:
    print(-1)
else:
    print(N - k)
### BUGGY CODE ###


import collections
S = input()
mod_list = []
mod_list.append(0)
for i in range(len(S)):
    x = int(S[i:])
    mod_list.append(x%2019)
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)

### FIXED CODE ###

import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)
### BUGGY CODE ###

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

dp =[[0 for i in range(n+2)] for j in range(n+2)]

for i in range(1):
    for j in range(i,n):
        t=0
        if s[j]=="C" and j!=i:
            if s[j-1]=="A":
                t=1
        
        dp[i][j]=dp[i][j-1]+t
        
for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        t=-1
    for j in range(n):
        dp[i][j]=max(dp[i-1][j]+t,0)
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

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