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

n = int(input())
S = [input() for i in range(n)]
for i in range(n):
  S[i] = sorted(S[i])
c = 0
for i in range(n):
  for j in range(i+1,n):
    if S[i] == S[j]:
      c += 1
print(c)

### FIXED CODE ###

n = int(input())
S = [input() for i in range(n)]
for i in range(n):
  S[i] = sorted(S[i])
S = sorted(S)
c = 0
i = 0
while i < n - 1:
  j = i + 1
  while j < n:
    if S[i] == S[j]:
      j += 1
    else:
      break
  c += (j-i) * (j-i-1) // 2
  i = j  
print(c)
### BUGGY CODE ###

H,W,D = map(int,(input().split()))

A = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,(input().split())))

d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i,j)

m = [0]*(H*W)
for i in range(1,H*W):
    if i+D <= H*W:
        m[i] = abs(d[i][0] - d[i+D][0]) + abs(d[i][1] - d[i+D][1])

Q = int(input())
for i in range(Q):
    L,R = map(int,(input().split()))
    ans = 0
    for j in range(L,R,D):
        ans += m[j]
    print(ans)

### FIXED CODE ###

H,W,D = map(int,(input().split()))

A = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,(input().split())))

d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i,j)

s = [[] for _ in range(D+1)]
for i in range(1,D+1):
    cost = 0
    s[i].append(0)
    for j in range(i,H*W-D+1,D):
        cost += abs(d[j][0] - d[j+D][0]) + abs(d[j][1] - d[j+D][1])
        s[i].append(cost)

Q = int(input())
for i in range(Q):
    L,R = map(int,(input().split()))
    r = L%D
    if r == 0:
        r = D
    ans = s[r][(R-r)//D]-s[r][(L-r)//D]
    print(ans)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
A = list(map(int, input().split()))
List = {}
for i in A:
    if List.get(i,None)==None:
        List[i]=1
    else:
        List[i]+=1

List_sorted = sorted(List.items(), key=lambda x:x[1])
tmp=0
Num=len(List_sorted)-K

for i in range(Num):
    tmp+=list(List_sorted[0])[1]
    del List_sorted[0]

print(tmp)


### FIXED CODE ###

import heapq

N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[0]*max(A)
ans=0
for item in A:
    l[item-1]+=1
    
heapq.heapify(l)

while len(l)>K:
    ans+=heapq.heappop(l)
    
print(ans)
### BUGGY CODE ###

def BinaryIndexSearch_floor(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] > p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[l] > p:
				return l
			elif SL[r] > p:
				return r
			else:
				return -1

		center = l + ((r-l) // 2)

		if SL[center] <= p:
			l = center + 1
			continue

		else:
			r = center
			continue

def BinaryIndexSearch_ceil(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] < p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[r] < p:
				return r
			elif SL[l] < p:
				return l
			else:
				return -1
		center = l + ((r-l) // 2)

		if SL[center] < p:
			l = center 
			continue

		else:
			r = center - 1
			continue

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N-2):
	for b in range(a+1, N-1):
		A = L[a]
		B = L[b]
		l = abs(A-B)
		r = A+B

		l_ind = BinaryIndexSearch_floor(l, L[b+1:])
		r_ind = BinaryIndexSearch_ceil(r, L[b+1:])

		if l_ind == -1 or r_ind == -1:
			continue
		else:
			ans += r_ind - l_ind + 1

print(ans)

### FIXED CODE ###

N = int(input())
L = sorted(list(map(int, input().split())))

def BinaryIndexSearch_floor(p, SL):
	"""
	search the minimum number among the larger numbers than the ginven nymber "n". 
	return the index of it under the list sorted.
	"""
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] > p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[l] > p:
				return l
			elif SL[r] > p:
				return r
			else:
				return -1

		center = l + ((r-l) // 2)

		if SL[center] <= p:
			l = center + 1
			continue

		else:
			r = center
			continue

def BinaryIndexSearch_ceil(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] < p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[r] < p:
				return r
			elif SL[l] < p:
				return l
			else:
				return -1
		center = l + ((r-l) // 2)

		if SL[center] < p:
			l = center 
			continue

		else:
			r = center - 1
			continue
ans = 0
for i in range(N-1):
	for j in range(i+1,N):
		wa = L[i] + L[j]
		sa = abs(L[i]-L[j])

		l = BinaryIndexSearch_ceil(wa,L)
		s = BinaryIndexSearch_floor(sa,L)

		oc = 0
		if s <= i <= l:
			oc += 1
		if s <= j <= l:
			oc += 1
		if l >= s:
			ans += max(0, l-s+1-oc)

print(ans//3)
### BUGGY CODE ###

import math


def calc(A, b):
    return sum(map(lambda x: abs(x-b), A))


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    left = min(A)
    right = max(A)

    while left < right:
        c1 = math.floor((left + left + right) / 3)
        c2 = math.ceil((left + right + right) / 3)
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))


if __name__ == "__main__":
    main()


### FIXED CODE ###


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    print(calc(A, sorted(A)[(N)//2]))

#    left = min(A)
#    right = max(A)
#
#    while left < right:
#        c1 = (left + left + right) // 3       # floor
#        c2 = -(-(left + right + right) // 3)  # ceil
#        if calc(A, c1) <= calc(A, c2):
#            right = c2 - 1
#        else:
#            left = c1 + 1
#    print(calc(A, left))


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

x, y, A, B, C = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a = sorted(a)[::-1]
b = sorted(b)[::-1]
c = sorted(c)

s = 0

a = a[:x]
b = b[:y]
s += sum(a)
s += sum(b)

a_nex = a.pop()
b_nex = b.pop()
c_nex = c.pop()

while True:
#     print(s)
    if a_nex > b_nex:
        if c_nex > b_nex:
            s = s - b_nex + c_nex
            if len(b) == 0:
                b_nex = int(2e9)
            else:
                b_nex = b.pop()
            if len(c) == 0:
                break
            c_nex = c.pop()

    if b_nex > a_nex:
        if c_nex > a_nex:
            s = s - a_nex + c_nex
            if len(a) == 0:
                a_nex = int(2e9)
            else:
                a_nex = a.pop()
            if len(c) == 0:
                break
            c_nex = c.pop()

    if c_nex <= a_nex and c_nex <= b_nex:
        break

print(s)

### FIXED CODE ###

from collections import deque
x, y, A, B, C = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a = sorted(a)[::-1]
b = sorted(b)[::-1]
c = sorted(c)

s = 0

a = a[:x]
b = b[:y]
s += sum(a)
s += sum(b)

a = deque(a)
b = deque(b)
c = deque(c)

a_nex = a.pop()
b_nex = b.pop()
c_nex = c.pop()

while True:
#     print(s)
    if a_nex > b_nex:
        if c_nex > b_nex:
            s = s - b_nex + c_nex
            if len(b) == 0:
                b_nex = int(2e9)
            else:
                b_nex = b.pop()
            if len(c) == 0:
                break
            c_nex = c.pop()
    else:
        if c_nex > a_nex:
            s = s - a_nex + c_nex
            if len(a) == 0:
                a_nex = int(2e9)
            else:
                a_nex = a.pop()
            if len(c) == 0:
                break
            c_nex = c.pop()

    if c_nex <= a_nex and c_nex <= b_nex:
        break

print(s)
### BUGGY CODE ###

import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,K= i_map()
	L = []
	R = []
	for i in range(0,K):
		tmpL,tmpR = i_map()
		L.append(tmpL)
		R.append(tmpR)

	a = []
	a.append(0)
	a.append(-1)
	for i in range(2,3*N):
		a.append(0)

	f = []
	f.append(1)

	for i in range(0,N):
		for j in range(0,K):
			a[i+L[j]] += f[i]
			a[i+R[j]+1] += -f[i]
		f.append(f[i]+a[i+1])

	print(f[N-1]%998244353)

	return

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,K= i_map()
	m = 998244353
	L = []
	R = []
	for i in range(0,K):
		tmpL,tmpR = i_map()
		L.append(tmpL)
		R.append(tmpR)

	a = []
	a.append(0)
	a.append(-1)
	for i in range(2,3*N):
		a.append(0)

	f = []
	f.append(1)

	for i in range(0,N):
		for j in range(0,K):
			a[i+L[j]] += f[i]
			a[i+R[j]+1] += -f[i]
		f.append((f[i]+a[i+1])%m)

	print(f[N-1]%m)

	return

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

from collections import deque
from itertools import product
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def dfs(i, j, k, N, dp):
    if any([i < 0, j < 0, k < 0, i + j + k > N]):
        return 0.0
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    x = 0.0
    x += dfs(i-1, j, k, N, dp) * (i / N)
    x += dfs(i+1, j-1, k, N, dp) * (j / N)
    x += dfs(i, j+1, k-1, N, dp) * (k / N)
    x += 1.0
    x *= N / (i + j + k)
    dp[i][j][k] = x
    return dp[i][j][k]


def solve(N, A):
    dp = [[[-1.0 for k in range(N + 2)] for j in range(N + 2)] for i in range(N + 2)]
    C = [0 for i in range(4)]
    for a in A:
        C[a] += 1
    dp[0][0][0] = 0.0
    return dfs(C[1], C[2], C[3], N, dp)


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

from collections import deque
from itertools import product
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def dfs(I, J, K, N, dp):
    for k in range(0, K+1):
        for j in range(0, J+K+1):
            for i in range(0, N+1):
                x = 0.0
                if not(i + j + k > N or i == 0 and j == 0 and k == 0):
                    x += dp[i-1][j] * (i / N) if i > 0 else 0.0
                    x += dp[i+1][j-1] * (j / N) if j > 0 else 0.0
                    x += dp[i][j+1] * (k / N) if k > 0 else 0.0
                    x += 1.0
                    x *= N / (i + j + k)
                dp[i][j] = x
    return dp[I][J]


def solve(N, A):
    dp = [[0.0 for j in range(N + 2)] for i in range(N + 2)]
    C = [0 for i in range(4)]
    for a in A:
        C[a] += 1
    return dfs(C[1], C[2], C[3], N, dp)


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
s=0
for i in range(A,B+1):
  if i%C!=0 and i%D!=0:
    s+=1
print(s)

### FIXED CODE ###

A,B,C,D=map(int,input().split())
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
def lcm(a,b):
  return (a*b)//gcd(a,b)
s=(A-1)//C
t=(A-1)//D
u=(A-1)//lcm(C,D)
v=s+t-u
w=A-1-v
S=B//C
T=B//D
U=B//lcm(C,D)
V=S+T-U
W=B-V
print(W-w)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
K = INT()

strings = set()
for i in range(1, len(s)+1):
	for j in range(len(s)-i+1):
		strings.add(s[j:j+i])
print(sorted(strings)[K-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	s = input()
	K = INT()

	strings = set()
	for i in range(1, K+1):
		for j in range(len(s)-i+1):
			strings.add(s[j:j+i])
	print(sorted(strings)[K-1])


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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
        print(answer if answer <= pow(10, 18) else -1)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_val = pow(10, 18)
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
            if max_val < answer:
                print(-1)
                break
        else:
            print(answer)


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

N = int(input())
S = input()
ans = 0
for i in range(1000):
    cnt = 0
    n = str(i).zfill(3)
    for c in S:
        if c == n[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

print(ans) 


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    cnt = 0
    n = str(i).zfill(3)
    for c in S:
        if c == n[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

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

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u].append([v,a,b])
    Graph[v].append([u,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
visited = [-1]*(N+1)
visited[0] = 1
que = []
# [time, nowhere, money, flag, visited]
heapq.heappush(que, [0, 1, S, 0])
ans = [-1]*(N+1)
Min = [[10**16]*5001 for i in range(N+1)]
#print(Graph)
while visited != [1]*(N+1):
    #print(que)
    time, nowhere, money, flag = heapq.heappop(que)
    #print(time, nowhere, money, flag)
    #route[nowhere] = 1
    Min[nowhere][min(money,5000)] = min(Min[nowhere][min(money,5000)], time)
    if visited[nowhere] == -1:
        visited[nowhere] = 1
        ans[nowhere] = time
    if flag == 0:
        c,d = City[nowhere-1]
        if money >= 5000:
            heapq.heappush(que, [time+d, nowhere, money+c, 1])
        else:
            heapq.heappush(que, [time+d, nowhere, money+c, 0])
    for (to,a,b) in Graph[nowhere]:
        #if not to in route:
        if money-a >= 0:
            if Min[to][min(money-a,5000)] > time+b:
                heapq.heappush(que, [time+b, to, money-a, flag])

for i in range(2,N+1):
    print(ans[i])

### FIXED CODE ###

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u-1].append([v-1,a,b])
    Graph[v-1].append([u-1,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
que = []
# [time, nowhere, money, flag, visited]
heapq.heappush(que, [0, 0, min(S,5000)])
ans = [[10**16]*5001 for i in range(N)]
#Min = [[10**16]*5001 for i in range(N+1)]
#print(Graph)
while que != []:
    time, nowhere, money = heapq.heappop(que)
    #print('here',time,nowhere,money)
    if time <= ans[nowhere][money]:
        ans[nowhere][money] = time
        c,d = City[nowhere]
        if time+d < ans[nowhere][min(5000,money+c)]:
            ans[nowhere][min(5000,money+c)] = time+d
            #print('to',time+d, nowhere, min(5000,money+c))
            heapq.heappush(que, [time+d, nowhere, min(5000,money+c)])
        for (to,a,b) in Graph[nowhere]:
            if 0 <= money - a and time+b < ans[to][min(5000,money-a)]:
                ans[to][min(5000,money-a)] = time+b
                #print('to',time+b, to, min(5000,money-a))
                heapq.heappush(que, [time+b, to, min(5000,money-a)])

for i in range(1,N):
    print(min(ans[i]))
### BUGGY CODE ###

A=input()
a=int(A)
n2=1
for i in range(a):
    for x in range(a):
        if n2 <= a:
            n1=(i+2)**(x+2)
            if n2 <= n1 and n1 <= a:
                n2 = n1
                #print(n2)
                n1
print(n2)

### FIXED CODE ###

A=input()
a=int(A)
b=round(a*(1/2))
n2=1
for i in range(2,b):
    for x in range(2,b):
        if n2 <= a:
            n1=(i)**(x)
            if n2 <= n1 and n1 <= a:
                n2 = n1
                #print(n2)
                n1
print(n2)
### BUGGY CODE ###

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
for _ in range(M):
    B, C = map(int, input().split(' '))
    A.extend([C]*B)
    A = sorted(A)[-N:]
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
BC_list = []
for _ in range(M):
    B, C = map(int, input().split(' '))
    BC_list.append((B, C))
BC_list = sorted(BC_list, key= lambda x: x[1], reverse=True)

for b, c in BC_list:
    A.extend([c]*b)
    if len(A) > 2*N:
        break
print(sum(sorted(A)[-N:]))
### BUGGY CODE ###

l,r=map(int,input().split())
mini = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    mini = min((i*j)%2019, mini)
    if mini == 0:
      break

print(mini)

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

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

n, *a = map(int, open(0).read().split())

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


### FIXED CODE ###

n, *a = map(int, open(0).read().split())

ans=[0]*(n)
for i, j in enumerate (a, 1):
  ans[j-1] = i
print(" ".join(map(str,ans)))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]

rui=[0]*(n+1)
for i in range(len(s)+1):
  rui[i] = s[0:i].count('AC')

for i in range(q):
  print(rui[lr[i][1]] - rui[lr[i][0]])


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]

rui=[0]*(n+1)
tmp=0
for i in range(len(s)):
  if s[i-1] == 'A' and s[i] == 'C':
    tmp += 1
  rui[i] = tmp

for i in range(q):
  print(rui[lr[i][1]-1] - rui[lr[i][0]-1])
### BUGGY CODE ###

n,q = map(int,input().split())
base = input()
ans=[]
for i in range(q):
    l,r = map(int,input().split())
    ans.append(str(base[l-1:r].count("AC")))
print('\n'.join(ans))

### FIXED CODE ###

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

counter = [0]*(n+1)
count=0
for i,s in enumerate(base):
    if i < n-1 and s=="A" and base[i+1]=="C":
        count+=1
    counter[i+1]=count

ans=[]
for i in range(q):
    l,r = map(int,input().split())
    ans.append(str(counter[r-1]-counter[l-1]))
print('\n'.join(ans))