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

s = int(input())
a = {s}
ai = s
i = 2
while True:
  if ai % 2 == 0:
    ai /= 2
  else:
    ai = 3 * ai + 1
  if ai in a:
    print(i)
    break
  else:
    i += 1


### FIXED CODE ###

s = int(input())
a = [0 for i in range(1000001)]
a[s] = 1
ai = s
i = 2
while True:
  if ai % 2 == 0:
    ai //= 2
  else:
    ai = 3 * ai + 1
  if a[ai] > 0:
    print(i)
    break
  else:
    a[ai] = 1
    i += 1
### BUGGY CODE ###

from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = lcm(A[0],A[1])
ans = Gcd//A[0]+Gcd//A[1]
temp = Gcd//A[1]
#print(temp)

for i in range(1,N-1):
    Gcd = lcm(A[i],A[i+1])
    temp2 = Gcd//A[i]
    Gcd2 = lcm(temp,temp2)
    #print(Gcd)
    #print(temp)
    #print(temp2)
    #print(Gcd2)
    a = Gcd2//temp
    b = Gcd2//temp2

    temp = Gcd//A[i+1]*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod
    #Gcd %= mod
    c = A[i+1]
    d = Gcd//c
    d %= mod
    ans += d*b
    #ans += Gcd//A[i+1]*b
    ans %= mod


print(ans)






### FIXED CODE ###

from fractions import gcd
import sys 
input = sys.stdin.readline

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = gcd(A[0],A[1])
ans = (A[0]//Gcd+A[1]//Gcd)%mod
temp = A[0]//Gcd

for i in range(1,N-1):
    #Gcd = lcm(A[i],A[i+1])
    Gcd = gcd(A[i],A[i+1])
    #temp2 = Gcd//A[i]
    temp2 = A[i+1]//Gcd
    #Gcd2 = lcm(temp,temp2)
    Gcd2 = gcd(temp,temp2)

    #a = Gcd2//temp
    a = temp2//Gcd2
    #b = Gcd2//temp2
    b = temp//Gcd2

    temp = A[i]//Gcd*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod


    Gcd %= mod #注意
    c = A[i]
    c %= mod
    d = c*pow_mod(Gcd,mod-2)
    #d = Gcd//c
    d %= mod


    e = b*d%mod
    ans += e
    #ans += Gcd//A[i+1]*b
    ans %= mod


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

def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = []
for i in range(len(primes)):
    if i <= 2:
        like_2017.append(0)
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(1)
    else:
        like_2017.append(0)
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(sum(like_2017[l:r+1]))


### FIXED CODE ###

def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r]-like_2017[l-1])
### BUGGY CODE ###

from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF

table = []
for i in range(N):
    d = dijkstra(N, i)
    table.append(d)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    ans = min(ans, t_dis)

print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    #print(each, t_dis)
    ans = min(ans, t_dis)

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

import sys
import numpy as np

read = sys.stdin.buffer.read

H,W,M = list(map(int, input().split()))

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
mxh_v = h.max()
mxw_v = w.max()
for i in np.where(h==mxh_v)[0]:
    for j in np.where(w==mxw_v)[0]:

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            d = 1
    if d == 1:
        break

print(a)

### FIXED CODE ###

H,W,M = list(map(int, input().split()))

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
y,z,ans = [[] for i in range(n+1)],[None for i in range(n+1)],"Yes"
for i,j,k in x:
	y[i].append([j,k])
	y[j].append([i,-k])
for i in range(1,n+1):
	if z[i] == None:
		z[i],q = 0,[i]
		while q:
			p = q.pop()
			for j,k in y[p]:
				if z[j] == None: q,z[j] = q+[j],z[p]+k
for i in range(1,n+1):
	for j,k in y[i]:
		if z[i]+k != z[j]: ans = "No"
print(ans)

### FIXED CODE ###

n,m = (int(i) for i in input().split())
y,z,ans = [[] for i in range(n+1)],[None for i in range(n+1)],"Yes"
for num in range(m):
	i,j,k = (int(i) for i in input().split())
	y[i].append([j,k])
	y[j].append([i,-k])
for i in range(1,n+1):
	if z[i] == None:
		z[i],q = 0,[i]
		while q:
			p = q.pop()
			for j,k in y[p]:
				if z[j] == None:
					q.append(j)
					z[j] = z[p]+k
for i in range(1,n+1):
	for j,k in y[i]:
		if z[i]+k != z[j]: ans = "No"
print(ans)
### BUGGY CODE ###

N, K, L = map(int, input().split())

class UnionFind():
  def __init__(self):
    self.par = [i for i in range(N)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

ufRoad = UnionFind()

for i in range(K):
  p, q = map(int, input().split())
  ufRoad.unite(p-1, q-1)

ufRail = UnionFind()

for i in range(L):
  r, s = map(int, input().split())
  ufRail.unite(r-1, s-1)

SRoad = [set() for i in range(N)]
SRail = [set() for i in range(N)]

for i in range(N):
  ufRoad.root(i)
  ufRail.root(i)

for i in range(N):
  SRoad[ufRoad.par[i]].add(i)
  SRail[ufRail.par[i]].add(i)

r = [0] * N
for i in range(N):
  r[i] = len(SRoad[ufRoad.par[i]] & SRail[ufRail.par[i]])

print(*r)

### FIXED CODE ###

N, K, L = map(int, input().split())

class UnionFind():
  def __init__(self):
    self.par = [i for i in range(N)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    self.par[self.root(y)] = self.root(x)

ufRoad = UnionFind()

for i in range(K):
  p, q = map(int, input().split())
  ufRoad.unite(p-1, q-1)

ufRail = UnionFind()

for i in range(L):
  r, s = map(int, input().split())
  ufRail.unite(r-1, s-1)

d = {}

for i in range(N):
  d[(ufRoad.root(i), ufRail.root(i))] = d.get((ufRoad.root(i), ufRail.root(i)), 0) + 1

r = [0] * N

for i in range(N):
  r[i] = d.get((ufRoad.root(i), ufRail.root(i)))

print(*r)
### BUGGY CODE ###

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

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

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
cum_list = [0]*(n+1)
a_flag = 0

for idx,i in enumerate(s,1):
    cum_list[idx] = cum_list[idx-1]
    if a_flag == 1 and i =='C':
        cum_list[idx] +=1
    if i == 'A':
        a_flag = 1
    else:
        a_flag = 0

for i in range(q):
    l, r = map(int, input().split())
    print(cum_list[r]-cum_list[l])
### BUGGY CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
AB = []
for a in range(min(K, len(A))):
    for b in range(min(K, len(B))):
        AB.append(A[a] + B[b])
AB = sorted(AB, reverse=True)
ABC = []
for ab in range(min(K, len(AB))):
    for c in range(min(K, len(C))):
        ABC.append(AB[ab] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

s=input()

max_len=0
tmp=""
for i in range(1,len(s)+1):
  arr=[s[:i]]
  for s_ in s[i:]:
    tmp+=s_
    if tmp != arr[-1]:
      arr.append(tmp)
      tmp=''
  max_len=max(max_len,len(arr))

print(max_len)

### FIXED CODE ###

s=input()

max_len=0
tmp=""

for i in range(1,min(len(s)+1,3)):
  last=s[:i]
  cnt=1
  for s_ in s[i:]:
    tmp+=s_
    if tmp != last:
      last=tmp
      tmp=''
      cnt+=1
  max_len=max(max_len,cnt)

print(max_len)
### BUGGY CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

#nCrの計算。nこの中から、r個を取り出す。
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

import copy


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

b = [0]*(n+1)
b[0] = 0
for i in range(1,n+1):
	b[i] = b[i-1] + a[i-1]

#print(b)

c = [0]*(n+1)
c = copy.copy(b)
c = list(set(c))
#print(c)

ans = 0

for i in c:
	#print(i)
	chk = b.count(i)
	#print(chk)
	if chk >= 2:
		ans = ans + combinations_count(chk,2)

print(ans)




### FIXED CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)


#nCrの計算。nこの中から、r個を取り出す。
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

import copy


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

b = [0]*(n+1)
b[0] = 0
for i in range(1,n+1):
	b[i] = b[i-1] + a[i-1]

#print(b)

#c = [0]*(n+1)
#c = copy.copy(b)
#c = list(set(c))
#print(c)

import collections
c = collections.Counter(b)
#print(c)
#print(c.values())

ans = 0

for i in c.values():
	#print(i)
	#chk = b.count(i)

	#print(chk)
	if i >= 2:
		ans = ans + i*(i-1)//2

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

import numpy as np
n = int(input())
coef = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if i == n-1:
        coef[i][0] = 1/2
        coef[i][-1] = 1/2
    else:
        coef[i][i] = 1/2
        coef[i][i+1] = 1/2
    
A = np.zeros((n, n))
for i in range(n):
    A[i] = coef[i]

b = np.array([int(x) for x in input().split()])

ans = np.linalg.solve(A, b)

print(" ".join(map(str, map(int, ans))))

### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]
S = sum(A)

X_1 = S
i = 0
while 2*i+1 < n:
    X_1 -= 2 * A[2*i+1]
    i += 1

X = [0] * n
X[0] = X_1

for i in range(n-1):
    X_i_1 = 2 * A[i] - X[i]
    X[i+1] = X_i_1
    
print(" ".join(map(str, X)))
### BUGGY CODE ###


import fractions as ft
#import math as ft


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // ft.gcd(a,lcm_)
#    print(lcm_)
    
ans = 0
bn = [0]*n
for i, a in enumerate(an):
    t = lcm_//a
    ans += t 
    ans %= prime

print(ans)

### FIXED CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

print(ans%prime)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Dec 19 10:03:26 2017

@author: kotania
"""
N = int(input())
AList = [0]*N

count = 0
        
for n in range(0,N):
    An = int(input())
    
    if An not in AList:
        AList.append(An)
        count += 1
    else:
        AList.remove(An)
        count -= 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Dec 19 10:03:26 2017

@author: kotania
"""
from collections import Counter

N = int(input())
 
AList = []
 
count = 0
        
for n in range(0,N):
    AList.append(input())
    
countDict = Counter(AList)
countDictValues = countDict.values()

count = 0

for c in countDictValues:
    if c % 2 == 1 :
        count += 1

print(count)
### BUGGY CODE ###

import bisect

s=input()
t=input()

index=list()
for a in range(len(t)):
 index.append([i for i, x in enumerate(s) if x == t[a]])

b=0
loop=0
condition=0

for j in range(len(t)):
  #print(j,index[j],b,c,loop)
  if len(index[j])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(index[j],b)
  if j<1:
    b=index[0][0]    
  elif c == len(index[j]): 
     loop +=1
     b=index[j][0]
  else:
     b=index[j][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)


        




### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

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

a = []
for i in range(n):
    line = [0 for j in range(n + 1)]
    line[i] = 1
    if i + 1 >= n:
        i = -1
    line[i + 1] = 1
    line[n] = d[i] * 2
    a.append(line)
#print(a)

for k in range(n):
    p = a[k][k]
    for j in range(k, n + 1):
        a[k][j]  = a[k][j] / p
    for i in range(n):
        if i != k:
            d = a[i][k]
            for j in range(k, n + 1):
                a[i][j] = a[i][j] - d * a[k][j]
ans = []
for i in range(n):
    ans.append(str(int(a[i][-1])))
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
bSum = 0
h = 1
for i in range(n):
    d[i] = d[i] * 2
    bSum = bSum + (d[i] * h)
    h = h * -1
m1 = bSum / 2

ans = [int(m1)]
for i in range(n - 1):
    ans.append(int(d[i] - ans[i]))
print(" ".join(map(str, ans)))
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  if d[i]**2==n:
    a.append([d[i], d[i]])
    continue
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  b = n // d[i]
  if b == d[i]:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if b == d[j]:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)
### BUGGY CODE ###

# input
N = int(input())
S = input()

# process
R = []
G = []
B = []
for i, s in enumerate(list(S)):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)

ans = 0
for r in R:
    for g in G:
        for b in B:
            i, j, k = r, g, b
            if i > j:
                i, j = j, i
            if i > k:
                i, j, k = k, i, j
            elif j > k:
                j, k = k, j

            if k-j != j-i:
                ans += 1

# output
print(ans)


### FIXED CODE ###

# input
N = int(input())
S = input()

# process
ans = S.count('R')*S.count('G')*S.count('B')
for i in range(N):
    for j in range(N):
        if i-j<0 or i+j >= N:
            break
        x = S[i-j]
        y = S[i]
        z = S[i+j]

        if x!= y and x != z and y != z:
            ans -= 1
            
# output
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
  l, r = map(int, input().split())
  print(s[l-1:r].count("AC"))

### FIXED CODE ###

import bisect
n, q = map(int, input().split())
s = input()
ac=[]
for i in range(n):
  if s[i:i+2] == "AC":
    ac.append(i)

for i in range(q):
  l, r = map(int, input().split())
  acl=bisect.bisect_left(ac,l-1)
  acr=bisect.bisect_left(ac,r-1)
  print(acr-acl)
### BUGGY CODE ###

S = input()
l = len(S)

count = 0
for i in range(l):
  for j in range(l):
    if i < j:
      new_s = int(S[i:j+1])
      if new_s % 2019 == 0:
        count += 1
      else:
        continue
    else:
      continue
print(count)

### FIXED CODE ###

from collections import Counter
S=input()[::-1]
mod=2019

X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10, i, mod)) % mod)

C = Counter(X)
ans = 0
for v in C.values():
    ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

	ans = [0] * Q
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

	ans = [0] * Q
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



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

N,Q=[int(x) for x in input().split()]
S=input()
Check_list=['A','T','G','C']

for i in range(Q):
  l,r=[int(x) for x in input().split()]
  S_temp=S[l-1:r]
  S_temp_list=S_temp.split('AC')
  
  ac_num=len(S_temp_list)-1
  
  print(ac_num)

### FIXED CODE ###

N,Q=[int(x) for x in input().split()]
S=list(input())

t=[0]

for i in range(1,N):
  if (S[i-1]=='A')&(S[i]=='C'):
    t.append(t[i-1]+1)
  else:
    t.append(t[i-1])

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