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



def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    A=[[1]*(W)for _ in range(H)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i,j,0))
            else:
                A[i][j]=0  
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            
            if 0<=nxt_i<=H-1:
                if 0<=nxt_j<=W-1:
                    if A[nxt_i][nxt_j]==0:
                        q.put((nxt_i,nxt_j,d+1))
                        A[nxt_i][nxt_j]=1
    print(d)

                
    
            

main()


### FIXED CODE ###

from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

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

N = int(input())
a = list(map(int, input().split()))
c1, c2, c3 = 0, 0, 0
for ai in a:
    if ai == 1:
        c1+=1
    elif ai == 2:
        c2 += 1
    else:
        c3 += 1
dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

for i in range(c3+1):
    for j in range(N+1):
        for k in range(N+1):
            if i>0 and j<N:
                dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
            if j>0 and k<N:
                dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
            if k>0:
                dp[i][j][k]+=(k/N)*dp[i][j][k-1]
            if  i+j+k == 0:
                continue
            dp[i][j][k]+=1
            dp[i][j][k]*=N/(i+j+k)
print(dp[c3][c2][c1])



### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+1)] for j in range(c3+1)]
    for i in range(c3+1):
        for j in range(c2+c3+1):
            for k in range(c1+c2+c3+1):
                if i+j+k>N:
                    continue
                if i>0 and j<c2+c3:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<c1+c2+c3:
                    dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
                if k>0:
                    dp[i][j][k]+=(k/N)*dp[i][j][k-1]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()
### BUGGY CODE ###

N, Q = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(Q)]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted([(lr[1], lr[0], i) for i, lr in enumerate(LR)])
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        if dp[i]<dp[x]+1:
            dp[i]=dp[x]+1
            f(i)
    return
for i in H:
    f(i)
print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
dp = [-1]*N


def dfs(n):
    if dp[n] > 0:
        return dp[n]

    ma = 0
    for b in G[n]:
        ma = max(ma, dfs(b) + 1)
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
dp = [-1]*N


def dfs(n):
    global dp
    if dp[n] > 0:
        return dp[n]

    ma = 0
    for b in G[n]:
        ma = max(ma, dfs(b) + 1)
    dp[n] = ma
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


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

import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline



def main():


    N ,K= map(int,input().split())
    H = list(map(int,input().split()))
    H = [0] + H
    dp= [0] *(N+1)
    dp = [10**5] * (N + 1)
    dp[1] = 0

    for i in range(2, N + 1):
        way =[10**10]*(K+2)
        for j in range(1, K+1):
            if j<i:
                way[j]=(dp[i-j]+abs(H[i]-H[i-j]))
        dp[i] = min(way)


    print(dp[N])





if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#import numpy as np
#from collections import defaultdict
#import math
#from collections import deque

input = sys.stdin.readline



def main():


    N ,K= map(int,input().split())
    H = list(map(int,input().split()))
    H = [0] + H
    dp= [0] *(N+1)
    dp = [10**5] * (N + 1)
    dp[1] = 0

    for i in range(2, N + 1):
        way =[10**10]*(K+2)
        for j in range(1, K+1):
            if j<i:
                way[j]=(dp[i-j]+abs(H[i]-H[i-j]))
        dp[i] = min(way)


    print(dp[N])





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

N=int(input())

arr=[]
for x in map(int,input().split()):
    tmp=[]
    i=0
    while x!=0:
        if x%2==1:
            tmp.append(i)
        i+=1
        x//=2
    arr.append(tmp)

ans=0
for i in range(N):
    tmp=1
    tarr=arr[i]
    for k in range(i+1,N):
        for x in tarr:
            if x in arr[k]:
                tarr=-1
                break
        if tarr==-1:
            break
        else:
            tmp+=1
            tarr+=arr[k]
    ans+=tmp
print(ans)

### FIXED CODE ###

N=int(input())

sum_=0
A =list(map(int,input().split()))
j=0
ans=0
sum_=0
for i in range(N):
    k=0
    while j<N and sum_+A[j]==sum_^A[j]:
        sum_+=A[j]
        ans+=j-i+1
        j+=1
    sum_-=A[i]
print(ans)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if Q<100000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

LR = list(map(int,input().split()))
L = LR[0]
R = LR[1]
Lis = []
for j in range(L,R+1):
    for i in range(L,j):
        Lis.append((i*j)%2019)
print(min(Lis))

### FIXED CODE ###

LR = list(map(int,input().split()))
L = LR[0]
R = LR[1]
K = 2018
if R - L> 2019:
    K = 0
else:
    for j in range(L,R+1):
        for i in range(L,j):
            if K > (i*j)%2019:
                K =  (i*j)%2019
print(K)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
a.sort()
cnt=0

while len(a)>0:
  item=min(a)
  t=a.count(item)
  #print(item,t,a)
  if t>item:
    cnt+=t-item
  elif t==item:
    pass
  else:
    cnt+=t
  del a[0:t]
  #print("after",a)
  
print(cnt)

### FIXED CODE ###

import collections

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

cnt=0

c=collections.Counter(a)
#print(c)

for item in c:
  t=c[item]
  if t>item:
    cnt+=t-item
  elif t==item:
    pass
  else:
    cnt+=t

#while len(a)>0:
#  item=a[0]
#  t=(item)
#  #print(item,t,a)
#  if t>item:
#    cnt+=t-item
#  elif t==item:
#    pass
#  else:
#    cnt+=t
#  del a[0:t]
#  #print("after",a)
  
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[13]:


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


# In[14]:


mod = 10**9+7
a_sum = sum(A)
mylist = [(a_sum-sum(A[:i+1]))*a for i,a in enumerate(A)]
ans = sum(mylist)%mod
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[23]:


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


# In[24]:


mod = 10**9+7
a_sum = sum(A)
a_sum_list = []
cnt = 0
for i,a in enumerate(A):
    a_sum_list += [a_sum-a-cnt]
    cnt += a
mylist = [a_sum_list[i]*a for i,a in enumerate(A)]
ans = sum(mylist)%mod
print(ans)


# In[ ]:
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=1
for i in range(1,N):
    if P[i]<=min(P[:i]):
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=1
minP=P[0]
for i in range(1,N):
    if minP>=P[i]:
        ans+=1
        minP=P[i]
print(ans)
### BUGGY CODE ###

import queue

n, m = map(int, input().split())

a = []
b = []

for i in range(m):
	s, t = map(int, input().split())
	a.append(s-1)
	b.append(t-1)

#各部屋から行ける部屋
c = [[] for i in range(n)]

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

q = queue.Queue()
q.put(0)
f = []

#部屋1からの距離
d = [10**6]*n
d[0] = 0

while not q.empty():
	x = q.get()
	if not(x in f):
		for i in c[x]:
			if not(i in f):
				q.put(i)
			d[i] = min(d[i], d[x]+1)
		f.append(x)

print('Yes')
for i in range(1,n):
	m = 10**6
	ans = 0
	for j in c[i]:
		if d[j]<m:
			m = d[j]
			ans = j+1
	print(ans)

### FIXED CODE ###

import queue

n, m = map(int, input().split())

a = []
b = []

for i in range(m):
	s, t = map(int, input().split())
	a.append(s-1)
	b.append(t-1)

#各部屋から行ける部屋
c = [[] for i in range(n)]

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

q = queue.Queue()
q.put(0)

#部屋1からの距離
inf = 10**8
d = [inf]*n
d[0] = 0
ans = [0]*n

while not q.empty():
	x = q.get()
	for i in c[x]:
		if d[i]==inf:
			q.put(i)
			d[i] = d[x]+1
			ans[i] = x+1

print('Yes')
for i in range(1,n):
	print(ans[i])
### BUGGY CODE ###

s=input()
t=input()
dp=[[""]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
print(dp[len(s)][len(t)])


### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

res=""
i=len(s); j=len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        res="".join([s[i-1],res])
        i-=1
        j-=1
print(res)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    s = list(input())
    ans = 0
    while(True):
        if s == [] or len(s) == 1:
            print(ans*2)
            return
        for i in range(1, len(s)):
            if (s[i-1]=='0' and s[i]=='1') or (s[i-1]=='1' and s[i]=='0'):
                ans += 1
                s.pop(i)
                s.pop(i-1)
                break
            if i == len(s)-1:
                print(ans*2)
                return
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    s = list(input())
    print(min(s.count('0'), s.count('1')) * 2)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
q = int(input())
def trans(s):
     return s[::-1]

def headto(s, c):
    return c+s

def endto(s, c):
    return s+c

for i in range(q):
    que = [i for i in input().split()]
    if que[0] == '1':
        s = trans(s)
    elif que[0] == '2':
        if que[1] == '1':
            s = headto(s,que[2])
        elif que[1] == '2':
            s = endto(s,que[2])
print(s)

### FIXED CODE ###

s = input()
q = int(input())
flag = True
head = '' # 最終的に先頭に追加されている文字
end = '' # 最終的に末尾に追加されている文字

for i in range(q):
    que = [i for i in input().split()]
    if que[0] == '1':
        flag ^= True # Trueなら通常，Falseは反転状態
    elif que[0] == '2' and flag is True:
        if que[1] == '1':
            head = que[2] + head
        elif que[1] == '2':
            end = end + que[2]
    elif que[0] == '2' and flag is False:
        if que[1] == '1':
            end = end + que[2]
        elif que[1] == '2':
            head = que[2] + head
s = head+s+end
if flag is False:
    s = s[::-1]
print(s)
### BUGGY CODE ###

a, b = map(int, input().split())


def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


list = [1]
if a % 2 == 0 and b % 2 == 0:
    list.append(2)

for i in range(3, min(a, b) + 1, 2):
    if a % i == 0 and b % i == 0:
        list.append(i)
cnt = 0


for i in list:
    if is_prime(i):
        cnt += 1
print(cnt + 1)



### FIXED CODE ###

a, b = map(int, input().split())


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


if a > b:
    num = gcd(a, b)
else:
    num = gcd(b, a)


def prime(n):
    i = 2
    table = set([])
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.add(i)
        i += 1
    if n > 1:
        table.add(n)
    return len(table)


print(prime(num)+1)
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
l=[]
for _ in range(a):
    l.append(1)
for _ in range(b):
    l.append(0)
for _ in range(c):
    l.append(-1)
print(sum(l[:k]))

### FIXED CODE ###

a,b,c,k=map(int,input().split())
'''l=[]
for _ in range(a):
    l.append(1)
for _ in range(b):
    l.append(0)
for _ in range(c):
    l.append(-1)
print(sum(l[:k]))'''
su=0
if a>=k:
    print(k)
else:
    su=su+a
    tem=k-a
    if b>=tem:
        print(su)
    else:
        tem1=tem-b
        print(su-tem1)
### BUGGY CODE ###

import numpy as np
import itertools
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, R= map(int, readline().split())
r = list(map(int,input().split()))
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = float("inf")

for town in itertools.permutations(r,R):
  tmp = 0
  for i in range(R-1):
    distance_mat = dijkstra(graph, directed = False, indices = town[i]-1)
    tmp += distance_mat[town[i+1]-1]
  ans = min(ans,tmp)

print(int(ans))

### FIXED CODE ###

def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  #print(r)
  #print(edge)
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  ans = float("inf")
  distance_mat = {}
  for i in r:
    distance_mat[i-1] = (dijkstra(graph, directed = False, indices = i-1))

  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()
### BUGGY CODE ###

X = input()
while X.count("ST") > 0:
  X = X.replace("ST", "")
print(len(X))

### FIXED CODE ###

X = input()
s_cnt, t_cnt = 0, 0
for i in range(len(X)):
  if X[i] == "S":
    s_cnt += 1
  elif s_cnt != 0:
    s_cnt -= 1
    t_cnt += 1
print(len(X) - 2*t_cnt)
### BUGGY CODE ###

mod=10**9+7
L=input()

sum=0
cnt=0
for i in range(len(L)):  
  if L[i] == "1":
    sum += (2**cnt)*(3**(len(L)-i-1))
    sum %= mod
    cnt += 1
    
sum += 2**cnt
sum %= mod
print(sum)

### FIXED CODE ###

mod=10**9+7
L=input()

m3=1
m3_list=[]
for i in range(len(L)):
  m3_list.append(m3)
  m3 = (3*m3)%mod                   
m3_list.reverse()
  
sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    #sum += cnt_2*(3**(len(L)-i-1))
    sum += cnt_2*m3_list[i]
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)
### BUGGY CODE ###

s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)

### FIXED CODE ###

s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)
### BUGGY CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def xyz(n: int) -> List[int]:
    rs = []
    for i in range(1, n + 1):
        r = 0
        for x in range(1, 100):
            for y in range(1, 100):
                for z in range(1, 100):
                    if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x > i:
                        break
                    elif x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == i:
                        r += 1
        rs.append(r)

    return rs


if __name__ == '__main__':
    main()


### FIXED CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    result = [0] * n
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                m = f(x, y, z)
                if m > n:
                    break
                result[m - 1] += 1

    return result


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

N, Q = map(int, input().split())
S = str(input())
#print(lr)

for i in range(Q):
  a, b = map(int, input().split())
  m = S[a-1:b]
  ans = m.count("AC")
  print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
t = [0] * (N+1)

for i in range(N):
  if S[i:i+2] == "AC":
    x = 1
  else:
    x = 0
  t[i+1] = t[i] + x

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