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

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
a = input()
b = input()
if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
    print("YES")
else:
    print("NO")
"""

#B
"""
n = I()
n = int(math.sqrt(n))
print(n**2)
"""

#C
"""
n = I()
a = LI()
a.sort()
b = LI()
b.sort()
c = LI()
c.sort()
ans = 0
for i in b:
    x = bisect.bisect_left(a, i)
    x = x * (n - bisect.bisect_right(c, i))
    ans += x
print(ans)
"""

#D
k = I()
ans = list(str(k))
ans = sum(list(map(int, ans)))
for i in range(2, 10**10):
    bk = list(str(k*i))
    bk = list(map(int, bk))
    ans = min(ans, sum(bk))
print(ans)

### FIXED CODE ###


#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def I(): return int(sys.stdin.readline())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = input()
    b = input()
    if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    n = I()
    n = int(math.sqrt(n))
    print(n**2)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    b = LI()
    b.sort()
    c = LI()
    c.sort()
    ans = 0
    for i in b:
        x = bisect_left(a, i)
        x = x * (n - bisect_right(c, i))
        ans += x
    print(ans)
    return

# D
# 解説AC
# 俺は正数問題を解いていたと思ったらいつのまにかグラフ問題を解いていた
# 何を言ってるかわからねーと思うが自分もわからねぇ(ｒｙ)
# 変態
# 全部の数字は足す1もしくは×10で考えられて前者なら全体の和が1増えて後者なら
# 変わらないということに気づいたらいけるんだと思う（いけるとは言ってない）
def D():
    k = II()
    dp = [inf] * k
    q = deque()
    q.append(1)
    dp[1] = 1
    while q:
        i = q.pop()
        if dp[(i * 10) % k] > dp[i]:
            dp[(i * 10) % k] = dp[i]
            q.appendleft((i * 10) % k)
        if dp[(i + 1) % k] > dp[i] + 1:
            dp[(i + 1) % k] = dp[i] + 1
            q.append((i + 1) % k)
    print(dp[0])
    return


#Solve
if __name__ == '__main__':
    D()
### BUGGY CODE ###

n, k = (int(i) for i in input().split())
balls = list(int(i) for i in input().split())
ball_set = set(balls)
freqs = list(balls.count(i) for i in ball_set)
freqs.sort(reverse=True)
print(sum(freqs[k:]))


### FIXED CODE ###

n, k = (int(i) for i in input().split())
balls = (int(i) for i in input().split())
freqs = {}
for ball in balls:
    freqs[ball] = freqs[ball] + 1 if ball in freqs else 1
freq_hist = list(freqs.values())
freq_hist.sort(reverse=True)
print(sum(freq_hist[k:]))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np

N, H = list(map(int, input().split()))
S = np.array([list(map(int, input().split())) for n in range(N)])
A = [[n, a] for n, a in enumerate(S[:, 0]) if max(S[:,0]) == a]
B = [n for n, b in enumerate(S[:, 1]) if b > A[0][1]]
sumB = sum(S[b,1] for b in B)
res = H - sumB

#print(S)
#print(A)
#print(B)
#print(sumB)
#print(res)

if res > 0:
    print((res-1)//A[0][1] + 1 + len(B))
else:
    L = sorted(S[B, 1])
    L.reverse()
    #print(L)
    p, q = 0, (len(L) - 1)
    while p != q:
        r = (p + q)//2
        #print(p, q, r)
        #print(L[:r + 1])
        if sum(L[:r + 1]) < H:
            p = r + 1
        else:
            q = r

    print(p + 1)
    
    #print(len(B))

### FIXED CODE ###

def main():
    N, H = map(int, input().split())

    A = [-1] * N
    B = [-1] * N
    for n in range(N):
        a, b = map(int, input().split())
        A[n] = a
        B[n] = b
    
    B.sort(reverse=True)
    max_A = max(A)
    
    count = 0
    for b in B:
        if max_A < b:
            H -= b
            count += 1
            if H <= 0:
                return count
        else:
            break
    return (H - 1) // max_A + 1 + count

print(main())
### BUGGY CODE ###

hako = []
zan = []
num = int(input())
for n in range(num):
  hako.append(int(input()))
for h in range(len(hako)):
  zan.append(hako[h])
  hako.remove(hako[h])
  print(max(hako))
  hako.insert(h, zan[h])

### FIXED CODE ###

num = int(input())
box = [int(input()) for _ in range(num)]
box_dash = sorted(box, reverse=True)
for b in box:
  if b == box_dash[0]:
    print(box_dash[1])
  else:
    print(box_dash[0])
### BUGGY CODE ###

#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])

### FIXED CODE ###

#135_D
s=input()
mod=10**9+7

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])
### BUGGY CODE ###

n = int(input())
l = []
for i in range(0,n):
    l.append(sorted(input()))

s = 0
for i in range(n-1):
  for k in range(i+1,n):
    if l[i] == l[k]:
      s +=1
 
print(s)

### FIXED CODE ###

n = int(input())
 
l = []
for i in range(n):
	l.append(sorted(str(input())))
 
d = sorted(l)
c = 0
ans = 0
for i in range(n-1):
	if d[i] == d[i+1]:
		c += 1
		ans += c
	else:
		c = 0
print(ans)
### BUGGY CODE ###

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

d = dict()

for a in A:
    d[a] = d.get(a, 0) + 1

for _ in range(int(input())):
    b, c = map(int, input().split())
    if d.get(b, 0) != 0:
        temp = d[b]
        d[b] -= temp
        d[c] = d.get(c, 0) + temp

    print(sum(k*v for k, v in d.items()))


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    sum_a = sum(A)

    d = dict()

    for a in A:
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        if d.get(b, 0) != 0:

            temp = d[b]         
            d[b] -= temp
            d[c] = d.get(c, 0) + temp

            sum_a += (c - b) * temp
        print(sum_a)
        
main()
### BUGGY CODE ###

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

for i in range(N):
    for j in range(i+1, N):
        sum_A += A[i]*A[j]
print(sum_A%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
sum_A = [0]*N
for j in range(N-1, 0, -1):
    sum_A[j] = A[j]+sum_A[(j+1) % N]
for i in range(N-1):
    ans += A[i]*sum_A[i+1]
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

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

import collections

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

def bfs(x0, y0):
    visited = [[0 for _ in range(w)] for _ in range(h)]
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

mxall = 0
for x0 in range(h):
    for y0 in range(w):
        if smat[x0][y0] == '.':
            mx = bfs(x0, y0)
            mxall = max(mxall, mx)
print(mxall)


### FIXED CODE ###

import collections

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

def bfs(x0, y0):
    visited = [[0 for _ in range(w)] for _ in range(h)]
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

if all(all(col == '.' for col in row) for row in smat):
    print((w - 1) + (h - 1))
else:
    mxall = 0
    for x0 in range(h):
        for y0 in range(w):
            if smat[x0][y0] == '.':
                mx = bfs(x0, y0)
                mxall = max(mxall, mx)
    print(mxall)
### BUGGY CODE ###

S=str(input())
Q=int(input())
for i in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        S=S[::-1]
    else:
        if T[1]=="1":
            S=T[2]+S
        else: S=S+T[2]
print(S)

### FIXED CODE ###

S1=""
S2=""
S=str(input())
Q=int(input())
flag=1
for i in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        flag*=-1
    else:
        if T[1]=="1":
            if flag==1:
                S1=T[2]+S1
            else: S2=S2+T[2]
        else:
            if flag==1:
                S2=S2+T[2]
            else:S1=T[2]+S1
if flag==1:
    S=S1+S+S2
else:S=S2[::-1]+S[::-1]+S1[::-1]
print(S)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a_ls = list(map(int, input().split()))
num_total = max(a_ls)
a_ls.remove(num_total)
Max = 0
for a in a_ls:
    c = combinations_count(num_total,a)
    if Max <= c:
        Max = c
        r = a
print(num_total,r)

### FIXED CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
if n > 2:
    a_ls.sort()
    num_total = a_ls[-1]
    a_ls.pop()
    def isOK(index, key, l):
        if l[index] >= key:
            return True
        else:
            return False
    def meguru_search(l, key):
        '''
        key以上の値を持つ最小のインデックスを返す
        '''
        left = -1
        right = len(l)

        while (right - left) > 1:
            mid = left + (right - left) // 2
            # 直感的に記憶　
                # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                    # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
                # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
            if isOK(mid, key, l):
                right = mid
            else:
                left = mid
        
        # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
        return right

    if num_total % 2 == 0:
        Max = num_total // 2
    else:
        Max = num_total // 2 + 1
    Maxind1 = meguru_search(a_ls, Max)
    Maxind2 = Maxind1 - 1
    abs_1 = abs(Max - a_ls[Maxind1])
    abs_2 = abs(Max - a_ls[Maxind2])
    if abs_1 > abs_2:
        r = a_ls[Maxind2]
    else:
        r = a_ls[Maxind1]
    print(num_total, r)
else:
    print(max(a_ls), min(a_ls))
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

ansListab=ansListab[:min(3001,x*y*z+1)]

ansList=[]
tmp=len(ansListab)
for i in range(tmp):
  for j in range(z):
    ansList.append(ansListab[i]+c[j])

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]*(N+1)
b = [0]*(M+1)

#累積和の計算
for i in range(1, N+1):
    a[i] = a[i-1] + A[i-1]
for j in range(1, M+1):
    b[j] = b[j-1] + B[j-1]

ans = 0
for i in range(N+1):
    left = 0
    right = M
    if K - a[i] < 0:
        break
    while left < right:
        mid = (left + right)//2
        if b[mid] < K - a[i]:
            left = mid + 1
        elif b[mid] > K - a[i]:
            right = mid - 1
    if b[left] <= K - a[i]:
        j = left
    else:
        j = left - 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]*(N+1)
b = [0]*(M+1)
for i in range(1, N+1):
    a[i] = a[i-1] + A[i-1]
for j in range(1, M+1):
    b[j] = b[j-1] + B[j-1]

ans = 0
j = M
for i in range(N+1):
    if K - a[i] < 0:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

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

place = 1
way = [1]
for i in range(1, n+1):
    if i == k:
        print(a[place-1])
        exit()
    if a[place-1] in way:
        break
    else:
        place = a[place-1]
        way.append(place)
ex = way.index(a[place-1])
loop = way[ex:]
if k <= ex:
    print(way[k])
else:
    k -= ex
    print(loop[k%len(loop)])


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
alr = [0 for i in range(n)]
now = 1
path = [now]

for i in range(k):
    now = a[now-1]
    # if now in path:
    #     now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
    #     break
    if alr[now-1] != 0:
        now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
        break
    path.append(now)
    alr[now-1] += 1

print(now)
### BUGGY CODE ###

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


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)
### BUGGY CODE ###

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

L.sort()
c=0
for i in range(n-2):
    for j in range(i+1,n-1):
        cl = L[i]+L[j]
        for k in range(j+1, n):
            if cl<=L[k]:
                break
            else:
                c+=1

print(c)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int,input().split()))

L.sort()
c=0
for i in range(n-2):
    ci=L[i]
    for j in range(i+1,n-1):
        cij = ci+L[j]
        c += bisect.bisect_left(L,cij,j+1,n)-j-1

print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""
import random

def quickselect(items, item_index):

    def select(lst, l, r, index):

        # base case
        if r == l:
            return lst[l]

        # choose random pivot
        pivot_index = random.randint(l, r)

        # move pivot to beginning of list
        lst[l], lst[pivot_index] = lst[pivot_index], lst[l]

        # partition
        i = l
        for j in range(l+1, r+1):
            if lst[j] < lst[l]:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]

        # move pivot to correct location
        lst[i], lst[l] = lst[l], lst[i]

        # recursively partition one side only
        if index == i:
            return lst[i]
        elif index < i:
            return select(lst, l, i-1, index)
        else:
            return select(lst, i+1, r, index)

    if items is None or len(items) < 1:
        return None

    if item_index < 0 or item_index > len(items) - 1:
        raise IndexError()

    return select(items, 0, len(items) - 1, item_index)

import numpy as np
N = int(input())
X = np.array(list(map(int, input().split(" "))))
for i in range(N):
    print(quickselect(np.append(X[:i], X[i+1:]), N//2-1))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""
import random
import copy

N = int(input())
X = list(map(int, input().split(" ")))
sorted_X = sorted(X)
med1 = sorted_X[N//2-1]
med2 = sorted_X[N//2]
for i in range(N):
    if X[i] <= med1:
        print(med2)
    else:
        print(med1)
### BUGGY CODE ###

def cnt(h,w):
  q=[]
  arr=[[True]*(w+2)]
  arr.extend([[True]+[s!='.' for s in input()]+[True] for _ in range(h)])
  arr.append([True]*(w+2))
  for i in range(1,h+1):
    for j in range(1,w+1):
      if arr[i][j]:
        q.append([i,j])
  ans=0
  while 1:
    nq=[]
    for y,x in q:
      if not arr[y-1][x]:
        nq.append([y-1,x])
        arr[y-1][x]=True
      if not arr[y][x-1]:
        nq.append([y,x-1])
        arr[y][x-1]=True
      if not arr[y+1][x]:
        nq.append([y+1,x])
        arr[y+1][x]=True
      if not arr[y][x+1]:
        nq.append([y,x+1])
        arr[y][x+1]=True
    if len(nq)==0:
      break
    else:
      q=nq
      ans+=1
  return ans
    
h,w=map(int,input().split())
print(cnt(h,w))

### FIXED CODE ###

import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break
### BUGGY CODE ###

a, b = map(int, input().split())
ans = a
for i in range(a+1, b+1):
    ans ^= i

print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
p, q = (a+1)//4, (b+1)//4
x, y = (a+1)%4, (b+1)%4
if abs(a-b) < 4:
    ans = a
    for i in range(a+1, b+1):
        ans ^= i
    print(ans)

else:
    if x == 0:
        ans = a

        if y == 1:
            ans ^= b
        elif y == 2:
            ans ^= b
            ans ^= (b-1)
        elif y == 3:
            ans ^= b
            ans ^= (b-1)
            ans ^= (b-2)
        elif y == 0:
            ans ^= 0

        print(ans)

    elif x == 1:
        ans = 0

        if y == 1:
            ans ^= b
        elif y == 2:
            ans ^= b
            ans ^= (b-1)
        elif y == 3:
            ans ^= b
            ans ^= (b-1)
            ans ^= (b-2)
        elif y == 0:
            ans ^= 0

        print(ans)

    elif x == 2:
        ans = a
        ans ^= (a+1)
        ans ^= (a+2)

        if y == 1:
            ans ^= b
        elif y == 2:
            ans ^= b
            ans ^= (b-1)
        elif y == 3:
            ans ^= b
            ans ^= (b-1)
            ans ^= (b-2)
        elif y == 0:
            ans ^= 0

        print(ans)

    elif x == 3:
        ans = a
        ans ^= (a+1)

        if y == 1:
            ans ^= b
        elif y == 2:
            ans ^= b
            ans ^= (b-1)
        elif y == 3:
            ans ^= b
            ans ^= (b-1)
            ans ^= (b-2)
        elif y == 0:
            ans ^= 0

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

num = int(input())
a = input()
count = 0
for i in range(num):
  if i < num-2 and a[i] == "#" and a[i+1] == ".":
    count += 1
    a = a[:i+1] + "#" + a[i+2:]
  elif i == num-2 and a[i] == "#" and a[i+1] == ".":
    count += 1
    a = a[:i+1] + "#"
print(count)

### FIXED CODE ###

n = int(input())
s=input()
if ('.' not in s) or ('#' not in s):
    print(0)
    exit()
bc = [0 for i in range(n)]
wc = [0 for i in range(n)]
for i in range(n):
  if s[i] == '#':
    bc[i] = 1
  else:
    wc[i] = 1
for i in range(n-1):
  bc[i+1] += bc[i]
for i in range(n-1,0,-1):
  wc[i-1] += wc[i]
ans = min(wc[0],bc[-1])
for i in range(n-1):
  ans = min(ans,bc[i]+wc[i+1])
print(ans)
### BUGGY CODE ###

import numpy as np
N, Q = map(int, input().split())
S = input()
po =[]
while True:
    if S.find("AC") == -1:
        break
    else:
        po.append(S.find("AC"))
        S =S.replace("AC","XX",1)
po_numpy = np.array(po)    
for i in range(Q):
    l1 ,r1 = map(int, input().split())
    print(np.sum(np.logical_and(l1-1<= po_numpy, po_numpy <= r1-2)))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        L[i+1] = L[i] +1
    else:
        L[i+1] = L[i]
for i in range(Q):
    l,r = map(int, input().split())
    print(L[r-1]-L[l-1])