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

def check_similar_num_2017(N, prime_lst):
    return (N in prime_lst) and ((N+1)//2 in prime_lst)

def get_prime_number_list(N):
    prime_lst = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return prime_lst + data
        prime_lst.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    prime_lst = get_prime_number_list(10**5)
    for _ in range(Q):
        cnt = 0
        l,r=map(int,input().split())
        for i in range(l, r+1, 2):
            cnt += check_similar_num_2017(i, prime_lst)
        print(cnt)

main()


### FIXED CODE ###

from itertools import accumulate

def get_prime_number_list(N):
    # N以下の素数のリストを返す
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0]*(10**5+10)
    tmp = [0]*(10**5+10)
    for prime in primes:
        prime_lst[prime] = 1
    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            tmp[i] = 1
    ans = list(accumulate(tmp))
    l_r = []
    for _ in range(Q):
        l_r.append(map(int,input().split()))
    for l,r in l_r:
        print(ans[r] - ans[l-1])

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 多分TLE
import numpy as np
from collections import deque
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    for j in range(i + 1, n):
        ans += (a[i] ^ a[j]) % mod
print(ans % mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
a = np.array(a)
ans = 0
# for bin_a in map(bin, a):
d = 1
num_of_one_per_keta = []
while d < (1 << 61):
    cnt = np.count_nonzero(a & d)
    num_of_one_per_keta.append(cnt)
    d <<= 1
ans = 0
for i, num_of_one in enumerate(num_of_one_per_keta):
    ans += (n-num_of_one)*num_of_one*pow(2, i, mod) % mod
print(ans % mod)
### BUGGY CODE ###

N = int(input())
str = input()
str_list=list(str)
answer_list=[]
for i in range (N):
  answer=0
  for j in range (N):
    if str_list[j] == "E":
      seki = -1
    else:
      seki = 1
    point = (j-i)*seki
    if point<0:
      answer = answer+1
  answer_list.append(answer)
print(min(answer_list))

### FIXED CODE ###

N = int(input())
str = input()
str_list=list(str)
num_list=[]
ans_list=[]
num=0
for i in range (N):
  if str_list[i]=="E":
    num=num+1
    num_list.append(num)
  else:
    num_list.append(num)
   
for i in range (N):
  if i==0:
    ans=num_list[N-1]-num_list[i]
    ans_list.append(ans)
  else:
    ans=num_list[N-1]-num_list[i]+i-num_list[i-1]
    ans_list.append(ans)

print(min(ans_list))
### BUGGY CODE ###

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(r2 + c2 + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

print(ans)

### FIXED CODE ###

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(r2 + c2 + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

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

from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = A
    num_cards = len(cards)
    for s in S:
        b = s[0]
        c = s[1]
        min_card_num = min(cards)
        if c > min_card_num:
            for _ in range(b):
                min_card_num = min(cards)
                if c > min_card_num:
                    for i in range(num_cards):
                        if cards[i] == min_card_num:
                            cards[i] = c
                            break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

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

N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
old_generation = set()
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    [old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and i not in old_generation:
                #print("unseen",i)
                next_generation.add(i)
    depth+=1
if len(old_generation) != N:
    print('No')
else:
    print('Yes')
    for node in range(1,N):
        neighbors = A[node]
        for i,neighbor in enumerate(neighbors):
            if neighbor == 1 and depth_list[i]<depth_list[node]:
                print(i+1)
                break
#print(depth_list)
        

### FIXED CODE ###

from collections import deque
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [] for _ in range(N)]
#node_info = [{'node':d,'connect':[],'depth':-1,'dir':-1} for d in range(N)]

for path in P:
    A[path[1]-1].append(path[0]-1)
    A[path[0]-1].append(path[1]-1)
#print(A)

previous = [-1 for i in range(N)]
previous[0]=0

que = deque([0])

while len(que) != 0:
    v = que.popleft()
    for v_i in A[v]:
        if previous[v_i] != -1:
            continue
        else:
            que.append(v_i)
            previous[v_i] = v
for i in range(N):
    if previous[i] == -1:
        print('No')
        exit()
print('Yes')
for i in range(1,N):
    print(previous[i]+1)
### BUGGY CODE ###

def MKNUMBER(ALL,l,r):
    number = ALL[l-1:r]
    return(number)
  
def countAC(number):
    count = 0
    flg = 0
    for i in number:
        if i == 0:
            flg = 0
        if i == 1:
            flg = 1
        if i == 2:
            if flg == 1:
                count = count + 1
            flg = 0
    print(count) 
    
N,Q = input().split()
N = int(N)
Q = int(Q)
S = input()
A=list(S)
ALL = []
for i in A:
        if i == "A":
            ALL.append(1)
        elif i == "C":
            ALL.append(2)
        else:
            ALL.append(0)
###print(ALL)
for i in range(0,Q):
    l,r = input().split()
    l = int(l)
    r = int(r)
    number = MKNUMBER(ALL,l,r)
    countAC(number)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
X = []
x = 0
check = 0
for i in S:
    if check == 1 and i == 'C':
        x += 1
        check = 0
    if i == 'A':
        check = 1
    else:
        check = 0
    X.append(x)
#print(X)
A = []
for _ in range(Q):
    l,r = map(int,input().split())
    ans = X[r-1] - X[l-1]
    A.append(ans)
for i in A:
    print(i)
### BUGGY CODE ###

L, R = map(int, input().split())
p = 2019

if L - R >= p:
    print(0)
else:
    res = p
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            res = min(res, i * j % p)
    print(res)

### FIXED CODE ###

L, R = map(int, input().split())
p = 2019

if R - L >= p:
    print(0)
else:
    res = p
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            res = min(res, i * j % p)
    print(res)
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [str(input()) for _ in range(n)]
num = Counter(s).most_common()[0][1]
ans = []
for i in range(len(Counter(s).most_common())):
    if Counter(s).most_common()[i][1] == num:
        ans.append(Counter(s).most_common()[i][0])
ans.sort()
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [str(input()) for _ in range(n)]
num = Counter(s)
ans = []
ma = max(num.values())
for i in sorted(num):
    if num[i] == ma:
        print(i)
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int,input().split()))
max_idx = 0
max_val = 0
for i in range(n-k+1):
    total = sum(p_list[i:i+k])
    if total > max_val:
        max_val = total
        max_idx = i

def exp(n):
    return 1+(n-1)*0.5

print(sum(map(exp, p_list[max_idx:max_idx+k])))

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int,input().split()))

from collections import deque
d=deque(p_list[:k])
max_val = sum(p_list[:k])
total = max_val
max_idx = 0

for i in range(k, n):
    num = p_list[i]
    total = total + num - d.popleft()
    if total > max_val:
        max_val = total
        max_idx = i-k+1
    d.append(num)

def exp(n):
    return 1+(n-1)*0.5

print(sum(map(exp, p_list[max_idx:max_idx+k])))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力の取得
A, B, N = list(map(int, input().split()))


def func(x: int) -> int:
    """目的関数

    Arguments:
        x {int} -- N以下の非負整数

    Returns:
        int -- 目的関数値
    """
    x_B = x / B
    return math.floor(A*x_B) - A*math.floor(x_B)


# 求解処理
result = 0
for x in range(min(N, B-1), N+1, B):
    result = max(result, func(x))

# 結果出力
print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力の取得
A, B, N = list(map(int, input().split()))


def f(x: int) -> int:
    return math.floor(A*x/B) - A*math.floor(x/B)


# 求解処理
result = f(min(B-1, N))

# 結果出力
print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        for k in range(L[j], R[j] + 1):
            if i - k >= 0:
                cnt += dp[i - k]
                cnt %= 998244353
            else:
                continue
    dp[i] = cnt

print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

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

N = int(input())
Al = [int(i) for i in input().split()]

ans = 0
divjl = []
sAl = sorted(Al)
for i in range(len(Al)):
    if i in divjl:
        continue
    flag = True
    for j in range(len(Al)):
        if i == j:
            continue
        if sAl[i] % sAl[j] == 0:
            flag = False
            divjl.append(j)
    if flag:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
Al = sorted([int(i) for i in input().split()])
maxAl = Al[-1]
markl = [-1] * (maxAl+1)

for i in Al:
    if markl[i] == 1:
        continue
    if markl[i] == 0:
        markl[i] = 1
        continue
    markl[i] = 0
    p = i*2
    while p <= maxAl:
        markl[p] = 1
        p += i
print(markl.count(0))
### BUGGY CODE ###

import sys
from functools import reduce
input = sys.stdin.readline

# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

if n == 10**4 and a[0] == 999983:
    print(874173244)
    exit()

lcm_ = a[0]
for i in range(n):
    lcm_ = lcm(lcm_, a[i])

b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

MAX = 1000001

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict()

# function to return a^n

def power(a, n):

    if n == 0:
        return 1
    p = power(a, n // 2) % mod
    p = (p * p) % mod

    if n & 1:
        p = (p * a) % mod
    return p

# function to find the smallest prime
# factors of numbers upto MAX


def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

# function to return the LCM modulo M


def lcmModuloM(arr, n):

    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:

        # LCM is product of primes to their
        # higest powers modulo M
        ans = (ans * power(i, max_map[i])) % mod
    return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)


def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

# Driver code
sieve()

# python > pypy
MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

a_list = [0 for _ in range(100005)]

for a in A_uniq:
    a_cnt = A.count(a)
    a_list[a] += a_cnt
    a_list[a+1] += a_cnt
    a_list[a+2] += a_cnt
    
            
print(max(a_list))   

### FIXED CODE ###

import numpy as np
from collections import Counter

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

ans = 0
counter = Counter(A)
for a, cnt in counter.most_common():
    tmp = counter[a-1] + cnt + counter[a+1]
    if ans < tmp:
        ans = tmp
        

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

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from functools import lru_cache

@lru_cache(None)
def solve(i,w):
    if i<0:
        return 0
    if w<WV[i][0]:
        return solve(i-1,w)
    return max(solve(i-1,w),solve(i-1,w-WV[i][0])+WV[i][1])

n,w=map(int,input().split())
WV=[tuple(map(int,input().split())) for _ in range(n)]
print(solve(n-1,w))

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,W=map(int,input().split())
max_v=10**5
DP=[0]+[float('inf')]*max_v #DP[i]: 価値iを達成するための最小重量
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(max_v,v-1,-1):
        DP[i]=min(DP[i],DP[i-v]+w)
ans=0
for v,w in enumerate(DP):
    if w<=W:
        ans=v
print(ans)
### BUGGY CODE ###

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = [An.count(i) for i in range(1,N+1)]
 
# 全部の組み合わせ
s = 0
for i in range(1,N+1):
    s += Cn[i-1]*(Cn[i-1]-1) // 2

for i in range(1,N+1):
    print(s - (Cn[An[i-1]-1] - 1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy

def main():
	num = int(input())
	
	clocks = []
	for _ in range(num):
		clock = int(input())
		clocks.append(clock)
		
	clock_max_i = clocks.index(max(clocks))
	times = copy.deepcopy(clocks)
	while True:
		flg = True
		max_num = max(times)
		for i, time in enumerate(times):
			if max_num == time : continue
			
			tmp = max_num // clocks[i]
			times[i] = clocks[i] * tmp
			if max_num != times[i]:
				flg = False
			
		if flg:
			print(times[0])
			sys.exit()
		else:
			times[clock_max_i] = times[clock_max_i] + clocks[clock_max_i]
			
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy

def main():
	num = int(input())
	
	clocks = []
	for _ in range(num):
		clock = int(input())
		clocks.append(clock)
		
	ans = 1
	for clock in clocks:
		ans = lcm(ans, clock)
	print(ans)
			
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

r,c,k = map(int,input().split())
b = [[0 for _ in range(c)] for _ in range(r)]
for i in range(k):
  y,x,v = map(int,input().split())
  y -= 1
  x -= 1
  b[y][x] = v

# dp[i][j][l]:(i,j)に居て、i行目のアイテムをl個拾ったときの価値最大値。
dp = [[[0 for _ in range(4)] for _ in range(c+1)] for _ in range(r+1)]
for i in range(r):
  for j in range(c):
    # アイテムを拾う遷移。個数が多い方から計算する。
    for l in range(2,-1,-1):
      dp[i][j][l+1] = max(dp[i][j][l]+b[i][j],dp[i][j][l+1])
    # 移動する遷移。行を移動する際は、拾ったアイテム数はリセットされる。
    for l in range(4):
      dp[i+1][j][0] = max(dp[i][j][l],dp[i+1][j][0])
      dp[i][j+1][l] = max(dp[i][j][l],dp[i][j+1][l])
ans = 0
for i in range(4):
  ans = max(dp[r-1][c-1][i],ans)
print(ans)

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline

  r,c,k = map(int,input().split())
  b = [[0 for _ in range(c)] for _ in range(r)]
  for i in range(k):
    y,x,v = map(int,input().split())
    y -= 1
    x -= 1
    b[y][x] = v

  # dp[j][l]:(i,j)に居て、i行目のアイテムをl個拾ったときの価値最大値。
  dp = [[0 for _ in range(4)] for _ in range(c+1)]
  for i in range(r):
    for j in range(c):
      # アイテムを拾う遷移。個数が多い方から計算する。
      for l in range(2,-1,-1):
        dp[j][l+1] = max(dp[j][l]+b[i][j],dp[j][l+1])
      # 移動する遷移。行を移動する際は、拾ったアイテム数はリセットされる。
      for l in range(4):
        dp[j+1][l] = max(dp[j][l],dp[j+1][l])
        dp[j][0] = max(dp[j][l],dp[j][0])
  ans = 0
  for i in range(4):
    ans = max(dp[c-1][i],ans)
  print(ans)

main()
### BUGGY CODE ###

# C - GeT AC
# https://atcoder.jp/contests/abc122/tasks/abc122_c
n, q = list(map(int, input().split()))

s = input()

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

cnt = []

for index in range(0, len(separators)):
    cnt.append(s[separators[index][0]-1:separators[index][1]].count('AC'))

for i in cnt:
    print(i)


### FIXED CODE ###

# C - GeT AC
# https://abc122.contest.atcoder.jp/tasks/abc122_c

"""
累積和を用いて実装しないと時間が足りない
"""

import sys
n, q = list(map(int, sys.stdin.readline().split()))
s = list(sys.stdin.readline())

cnt = [0] * (len(s)+1)

"""
ACを数えるために受けた文字列ｓを展開して数えていく
"""

for i in range(1, len(s)):
    """
    s = ACACTACG
    cnt = [0,0,1,1,2,2,2,3,3]
    i == 1, 2, 3……len(s)
    
    i == 1
    s[i] == C s[i-1] == A
    ここで代入されるべきなのはcntのindex2番である　
        なぜならば、cntは最初に0を代入するので、s[i]の位置に当たるのはcnt[i]+1であるため
    """

    if s[i] == "C" and s[i-1] == "A":
        cnt[i+1] = cnt[i] + 1
    else:
        cnt[i+1] = cnt[i]


r_and_l = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

for e in r_and_l:
    num = e[0]
    print(cnt[e[1]] - cnt[num] )
### BUGGY CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while dp[i][j] != 0:
  if dp[i - 1][j - 1] != dp[i][j]:
    result = s[i - 1] + result
    i -= 1
    j -= 1
  else:
    if dp[i - 1][j] == dp[i][j] and i != 0:
      i -= 1
    else:
      j -= 1
print(result)

### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

n = int(input())
list = list(input())
lisr_r = list[::-1]
list_len = len(list)
ans = 0

while True:
  if 'W' not in list or 'R' not in list:
    break

  w = list.index('W')
  r = lisr_r.index('R')

  if w > list_len - 1 - r:
    break

  list[w] = 'R'
  lisr_r[r] = 'W'

  ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
list = input()
count_r = list.count('R')
ans = list[:count_r].count('W')

print(ans)