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

import sys
input=sys.stdin.readline
N=int(input())
S=input()[:-1]
c=N*2
for i in range(N+1):
  c = min(c,S[:i].count('#')+S[i:].count("."))
print(c)


### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
S=input()
w=S.count('.')
c=w
for i in range(N):
  if S[i]=='.':
    w-=1
  else:
    w+=1
  c=min(c,w)
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

x = int(input())

for i in range(1, x+1):
    if x % i != 0:
        continue
    else:
        for a in range(x):
            b = a - i
            if a**5 - b**5 == x:
                ans_a = a
                ans_b = b
                break
        if a**5 - b**5 == x:
            break

print(ans_a, ans_b)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

x = int(input())
flg = 0

for i in range(1, x+1):
    if x % i != 0:
        continue
    else:
        for a in range(x):
            b = a - i
            if a**5 - b**5 == x:
                ans_a = a
                ans_b = b
                flg = 1
                break
            elif a > i and a**5 - b**5 > x:
                flg = -1
                break
        if flg == 1:
            break
        elif flg == -1:
            flg = 0
            continue

print(ans_a, ans_b)
### BUGGY CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

M = max(ok)

for i in ok:
    for j in range(2,M+1):
        mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

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

x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
a,b=2*y-x,2*x-y
if a<0 or b<0:
  print(0)
elif a%3!=0 or b%3!=0:
  print(0)
else:
  a//=3
  b//=3
  print(comb(a+b,a))


### FIXED CODE ###

x,y=map(int,input().split())
mod=10**9+7
n_max=10**6+1
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
a,b=2*y-x,2*x-y
if a<0 or b<0:
  print(0)
elif a%3!=0 or b%3!=0:
  print(0)
else:
  a//=3
  b//=3
  print(comb(a+b,a))
### BUGGY CODE ###

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

#dp[l][r] = [l, r)区間のスライムを
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    else:
        res = float("inf")
        if (r - l) == 1:
            dp[l][r] = 0
            return dp[l][r]
        for k in range(l, r):
            if k == l or k == r:
                continue
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

### FIXED CODE ###

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])
### BUGGY CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
neo_b = [[] for _ in range(n)]
ans = 0
for i in range(n):
  neo_b[i] = bisect.bisect_left(a,b[i])
for i in range(n):
  ans += sum(neo_b[:bisect.bisect_left(b,c[i])])
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(n):
  ans += bisect.bisect_left(a,b[i])*(n-bisect.bisect_right(c,b[i]))
print(ans)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A = list(map(int, input().split()))
ref = list(combinations(A, 2))
res = 0

for i in range(len(ref)):
  a, b = ref[i]
  res += ((a * b) % (10 ** 9 + 7))
print(res % (10 ** 9 + 7))

### FIXED CODE ###

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

res = 0
sums = sum(A)
for i in range(len(A)):
  sums = sums - A[i]
  a = A[i]
  res += ((a * sums) % (10 ** 9 + 7))
print(res % (10 ** 9 + 7))
### BUGGY CODE ###

n=int(input())
l1=sorted(list(map(int,input().split())))
m=int(input())
l2=sorted(list(map(int,input().split())))
def nibutan(a,k):
    l=0
    r=len(a)
    while r>l:
        m=(r+l)//2
        if a[m]==k:
            return m
        elif k<a[m]:
            r=m
        else:
            l=m
    return -1
c=0
for i in l2:
    if nibutan(l1,i)!=-1:
        c+=1
print(c)


### FIXED CODE ###

n=int(input())
l1=sorted(list(map(int,input().split())))
m=int(input())
l2=sorted(list(map(int,input().split())))
def nibutan(a,k):
    l=0
    r=len(a)
    while r>l:
        m=(r+l)//2
        if a[m]==k:
            return m
        elif k<a[m]:
            r=m
        else:
            l=m+1
    return -1
c=0
for i in l2:
    if nibutan(l1,i)!=-1:
        c+=1
print(c)
### BUGGY CODE ###


N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        
        if j < wv[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]] + wv[i-1][1])

print(dp[N][W])


### FIXED CODE ###


N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        
        if j < wv[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]] + wv[i-1][1])

print(dp[N][W])
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = ""
for i in range(N-L+1):
    ans += str(min(A[i:i+L])) + " "
print(ans[:-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

def main():
    S = input()
    # 全探索
    count = 0
    for i in range(len(S)-3):
        for j in range(i+4,len(S)+1,1):
            if int(S[i:j])%2019==0: count+=1
    print(count)

main()


### FIXED CODE ###

def main():
    S = input()
    n = len(S)
    p = 2019 # 法p
    # (1) a≡b,c≡dならばa+c≡b+d
    # (2) aと法pが互いに素である時、ab≡acならばb≡c
    # ex).S=1817181712114(idxは最下位が0とする), n=len(S)
    # 4≡4%p <- modp[0]
    # 14=10+4≡10%p+modp[0] <- modp[1]
    # 114=100+14≡100%p+modp[1] <- modp[2]
    # 2114=2000+114≡2000%p+modp[2] <- modp[3]
    # ...
    # 1817181712114≡100000000000%p+modp[n-2] <- modp[n-1]
    # したがって、S[1:4]=21%pについては
    # 2100=2114-14≡modp[3]-modp[1]
    # ここでaとpが互いに素なので(a=100,p=7)
    # 2100≡21 が言える
    # よって21≡modp[3]-modp[1]
    # 一般化すると、
    # S[i:j+1]≡modp[j]-modp[i]
    # すなわちmodp[j]==modp[i]となるi,jを選んだ時、S[i:j+1]はpで割り切れるという事になる

    # Sをreverseする
    S = [S[i] for i in range(n-1,-1,-1)]
    # modpを作成
    modp_counter = [0] * p
    modp = 0
    modp_counter[0] = 1 # 割り切れるやつが入る場所の初期値を1にしておかないと、1つ割り切れるやつがきたときにpair_count+=0となってしまう(pair_count+=1になるべきなのに)
    pair_count = 0
    d = 1
    for s in S:
        modp = (int(s)*d%p+modp)%p
        pair_count += modp_counter[modp]
        modp_counter[modp] += 1
        d *= 10
        d %= p # 計算量削減
    print(pair_count)


main()
### BUGGY CODE ###

from fractions import gcd
lcm = lambda x,y: x*y//gcd(x,y)
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
p = 1
for a in A:
    b = lcm(a, p)
    ans = (ans * (b // p) % MOD + (b // a))%MOD
    p = b
print(ans)

### FIXED CODE ###

from fractions import gcd
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
p = 1
for a in A:
    b = gcd(a,p)
    ans = (ans * (a//b) % MOD + (p//b))%MOD
    p = a*p//b
print(ans)
### BUGGY CODE ###

N,K = map(int, input().strip().split(' '))
x = list(map(int, input().strip().split(' ')))
min_cost = float('inf')
for i in range(N-K+1):
  now = x[i:i+K]
  n_cost = abs(min(now[0], 0))
  p_cost = max(0, now[-1])
  cost = n_cost + p_cost + min(n_cost, p_cost)
  if min_cost > cost:
    min_cost = cost
print(min_cost)

### FIXED CODE ###

N,K = map(int, input().strip().split(' '))
x = list(map(int, input().strip().split(' ')))
min_cost = float('inf')
if N > 2*K:
  for i,d in enumerate(x):
    if d >= 0:
      break
  x = x[i-K:i+K]
for i in range(len(x)-K+1):
  n_cost = -min(x[i], 0)
  p_cost = max(0, x[i+K-1])
  cost = n_cost + p_cost + min(n_cost, p_cost)
  if min_cost > cost:
    min_cost = cost
print(min_cost)
### BUGGY CODE ###

n=int(input())
a=[]
ans=0
for i in range(n):
    x=int(input())
    if a.count(x)==0:
        a.append(x)
    else:
        del a[a.index(x)]
print(len(a))


### FIXED CODE ###

n=int(input())
d={}
ans=0
for i in range(n):
    a=int(input())
    try:
        if d[a]%2==0:
            ans+=1
            d[a]+=1
        else:
            ans-=1
            d[a]+=1
    except:
        d[a]=1
        ans+=1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=sorted(LI(),reverse=True)
B=sorted(LI(),reverse=True)
C=sorted(LI(),reverse=True)
Q=[[(A[0]+B[0]+C[0])*(-1),0,0,0]]
heapify(Q)
#print(Q)
i=0
ans=[]
#print(heappop(Q))
#al=[[[-1]*x for i in range(y)] for j in range(z)]
#al[0][0][0]=0
xl,yl,zl=0,0,0
al=[]
al=[[0,0,0]]
while i<k:
    #print(Q)
    if not Q:
        sys.exit()
    a,u,v,w=heappop(Q)
    ans.append(-a)
    i+=1
    if u+1<x and (not ([u+1,v,w] in al)):
        heappush(Q,[-A[u+1]-B[v]-C[w],u+1,v,w])
        al.append([u+1,v,w])
        
        #al[u+1][v][w]=0
    if v+1<y and not([u,v+1,w] in al):
        heappush(Q,[-A[u]-B[v+1]-C[w],u,v+1,w])
        al.append([u,v+1,w])
        #al[u][v+1][w]=0
    if w+1<z and not([u,v,w+1] in al):
        heappush(Q,[-A[u]-B[v]-C[w+1],u,v,w+1])
        al.append([u,v,w+1])
#print(len(ans))
for i in range(k):
    print(ans[i])

    
    


### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=LI()
B=LI()
C=LI()
lis=[]
for i in range(x):
    for j in range(y):
        lis.append(A[i]+B[j])
lis.sort(reverse=True)
lisan=[]
for i in range(min(k,x*y)):
    for j in range(z):
        lisan.append(lis[i]+C[j])
lisan.sort(reverse=True)
for i in range(k):
    print(lisan[i])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        if c > a[j]:
            a[j] = c
        else:
            break

    a.sort()

print(sum(a))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    AF = [(a, f) for a, f in zip(sorted(A), sorted(F, reverse=True))]

    def isOk(T):
        ret = 0
        for a, f in AF:
            m = T // f
            if a > m:
                ret += a - T // f
        return ret <= K

    ok = max(A) * max(F)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid

    print(ok)

sol()


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]

ds = [[-1]*w for _ in range(h)]

vectors = [(-1,0),(1,0),(0,-1),(0,1)]

stack = []

ans = 0

visited = [[False]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
            ds[i][j] = 0

while stack:
    nh,nw = stack.pop(0)
    for vh,vw in vectors:
        if nh+vh>=0 and nh+vh<h and nw+vw>=0 and nw+vw<w:
            if ds[nh+vh][nw+vw] == -1:
                stack.append((nh+vh,nw+vw))
                ds[nh+vh][nw+vw] = ds[nh][nw] + 1
                ans = ds[nh][nw] + 1

print(ans)


### FIXED CODE ###

import numpy as np
import copy

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[0 if (ai[j] == "#") else np.inf for j in range(w)] for ai in a])

for i in range(1, h):
    a[i] = np.minimum(a[i], a[i - 1] + 1)
for i in range(h - 2, -1, -1):
    a[i] = np.minimum(a[i], a[i + 1] + 1)
for i in range(1, w):
    a[:, i] = np.minimum(a[:, i], a[:, i - 1] + 1)
for i in range(w - 2, -1, -1):
    a[:, i] = np.minimum(a[:, i], a[:, i + 1] + 1)

print(int(a.max()))
### BUGGY CODE ###

import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,m = Is()
s = set(range(1,n+1))
for i in range(m):
    l,r = Is()
    s = s & set(range(l,r+1))
print(len(s))

### FIXED CODE ###

import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,m = Is()
left,right = 0,n
for i in range(m):
    l,r = Is()
    left = max(left,l)
    right = min(right,r)
#    print(left,right)
if right-left < 0:
    print(0)
else:
    print(right-left+1)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
max_count = 0
for i in range(0, N-1):
  tmp_count = 0
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      tmp_count=tmp_count+1
    else:
      break
  if tmp_count>max_count:
    max_count=tmp_count
  if max_count >= N-i:
    break
print(max_count)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
tmp = 0
s = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    tmp += 1
    s = max(s, tmp)
  else:
    tmp = 0
    
print(s)
### BUGGY CODE ###

q = int(input().rstrip())
ans = []
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans.append(dp1[-1])
print(*ans, sep="\n")


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

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

num_list = [0 for i in range(N)]


for n in A :
  num_list[n-1] += 1

for k in range(N) :
  ans = 0
  num_list[A[k]-1] -= 1
  for nums in num_list :
    if(nums != 0) :
      ans += int(nums*(nums-1)/2)
  print(ans)
  num_list[A[k]-1] += 1

### FIXED CODE ###

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

num_list = [0 for i in range(N)]


for n in A :
  num_list[n-1] += 1
  
calc_list = list(map(lambda x : max(0, int(x*(x-1)/2)), num_list))
s = sum(calc_list)

for k in range(N) :
  print(s - num_list[A[k]-1] + 1)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
"""
points = []
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    points.append(i)
for _ in range(Q):
  r, l = map(int,input().split())
  List = [n for n in points if n >= r -1 and n+1 <= l-1]
  print(len(List))
"""
for i in range(Q):
  r, l = map(int,input().split())
  S_short = S[r-1:l]
  counter = 0
  for j in range(len(S_short)-1):
    if S_short[j]=='A' and S_short[j+1] == 'C':
      counter +=1
  print(counter)


### FIXED CODE ###

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

K, N = map(int, input().split())
P = 998244353


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume = (nume * (n - i + 1)) % P
        deno = (deno * i) % P
    deno_inv = pow(deno, P-2, P)
    return nume*deno_inv


for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K-i+1, i-K-1)
    for j in range(n_pair+1):
        not_use = comb(n_pair, j)
        which_use = pow(2, n_pair - j, P)
        dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        ans = (ans + not_use * which_use * dice_cnt) % P
        n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    if i % 2 == 0:
        for j in range(n_pair+1):
            not_use = comb(n_pair, j)
            which_use = pow(2, n_pair - j, P)
            dice_cnt = comb(N - 1 + out_pair-1, n_pair - j - 1 + out_pair)
            ans = (ans + not_use * which_use * dice_cnt) % P
    print(ans)


### FIXED CODE ###

import sys

K, N = map(int, input().split())
P = 998244353


kaizyo = [0]
kaizyo_inv = [0]
tmp = 1
for i in range(1, N+K):
    tmp = (tmp*i) % P
    kaizyo.append(tmp)
    kaizyo_inv.append(pow(tmp, P - 2, P))


def comb(n, r):
    if n < r or r < 0:
        return 0
    elif n == r or r == 0:
        return 1
    else:
        return kaizyo[n] * kaizyo_inv[r] * kaizyo_inv[n - r]


inv_2 = pow(2, P - 2, P)
anss = ''
for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K - i + 1, i - K - 1)
    which_use = pow(2, n_pair+1, P)
    for j in range(n_pair + 1):
        if n_pair - j > N:
            which_use = (which_use * inv_2) % P
            continue
        not_use = comb(n_pair, j)
        which_use = (which_use * inv_2) % P
        dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        if i % 2 == 0:
            dice_cnt = (dice_cnt + comb(N - 2 + out_pair,
                                        n_pair - j - 1 + out_pair)) % P
        tmp = (not_use * which_use) % P
        tmp = (tmp * dice_cnt) % P
        ans = (ans + tmp) % P
    anss += str(ans) + '\n'
print(anss.rstrip())
### BUGGY CODE ###

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

def serarch(num, target):
    first = 0
    last = len(target)
    while last - first > 1:
        if target[int((last + first)/2)] > num:
            last = (last + first)/2
        else:
            first = (last + first)/2
    return int(last)


a.sort()

for i in range(M):
    b = bc[i][0]
    c = bc[i][1]

    idx = serarch(c, a)
    change_id = min(idx, b)
    a = a[change_id:idx] + [c for i in range(change_id)] + a[idx:]

print(sum(a))

### FIXED CODE ###

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

a.sort()
bc.sort(key=lambda x:x[1],reverse=True)

cnt = 0
for i in range(M):
    b = bc[i][0]
    c = bc[i][1]
    a.extend([c for i in range(b)])
    cnt += b
    if cnt > N:
        break

a.sort(reverse=True)
print(sum(a[:N]))