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

x =int(input())
credit = 100
year = 0


for i in range(10**18):
 #credit = int(credit * 1.01)
  credit = credit // 100
  if(x <= credit):
    break
print(year)
  
      

### FIXED CODE ###

x =int(input())
credit = 100
year = 0


for i in range(10**18):
 #credit = int(credit * 1.01)
  year +=1
  credit += credit // 100
  if(x <= credit):
    break
print(year)
### BUGGY CODE ###

def main():

    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[0][0] = 0
    # for i in range(N): dp[i][0] = 0
    # for j in range(M): dp[0][j] = 0

    for i in range(N):
        for j in range(M):
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= mod
    # print(dp)
    return dp[N][M] + 1

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():

    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[0][0] = 0
    # for i in range(N): dp[i][0] = 0
    # for j in range(M): dp[0][j] = 0

    for i in range(N):
        for j in range(M):
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= mod
    # print(dp)
    return dp[N][M] + 1

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

import sys
sys.setrecursionlimit(1000000)

def gcd(i,j):
  if i>j:
    i,j=j,i
  if j%i==0:
    return i
  return gcd(j-i,i)

n=int(input())
l=[int(i) for i in input().split()]
g=gcd(l[0],l[1])
for i in range(2,len(l)):
  g=gcd(g,l[i])
print(g)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def gcd(i,j):
  if i>j:
    i,j=j,i
  if j%i==0:
    return i
  return gcd(j-i,i)

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
g=gcd(l[0],l[1])
for i in range(2,len(l)):
  g=gcd(g,l[i])
print(g)
### BUGGY CODE ###

n = int(input(), 10)
a = list(map(int, input().split()))
greatCDlist = []


def gcd(m, n):
    if m < n:
        m ^= n
        n ^= m
        m ^= n
    if n == 0:
        return m
    else:
        return gcd(n, m % n)


for i in range(n):
    pop = a.pop(i)
    greatCD = 1
    for j in range(n-1):
        if j == 0:
            greatCD = a[0]
        else:
            greatCD = gcd(greatCD, a[j])
    a.insert(i, pop)
    greatCDlist.append(greatCD)

maxg = 1
for i in range(n):
    if maxg < greatCDlist[i]:
        maxg = greatCDlist[i]

print(maxg)


### FIXED CODE ###

n = int(input(), 10)
a = list(map(int, input().split()))
greatCDlist = []


def gcd(m, n):
    if m < n:
        m ^= n
        n ^= m
        m ^= n
    if n == 0:
        return m
    else:
        return gcd(n, m % n)


left = [0 for i in range(n+1)]
right = [0 for i in range(n+1)]

for i in range(n):
    left[i+1] = gcd(left[i], a[i])


for i in range(n-1, -1, -1):
    right[i] = gcd(right[i+1], a[i])


result = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    result = max(result, gcd(l, r))

print(result)
### BUGGY CODE ###

N = int(input())
A_list = []
for i in range(1,N+1):
    A = int(input())
    A_list.append([i,A])

pop_que =[]

for i in range(1,N+1):
    pop_que =A_list.pop(0)
    pop_que.append(max(A_list,key=lambda x:x[1]))
    A_list.append(pop_que)
    print(A_list[-1][2][1])

#for i in range(N):
#    print(A_list[i][2][1])


### FIXED CODE ###

N = int(input())
A_list = []
for i in range(1,N+1):
    A = int(input())
    A_list.append(A)
A_list_sort = sorted(A_list)

max_a = A_list_sort[-1]
max_b = A_list_sort[-2]


for i in range(N):
    if A_list[i] == max_a:
        print(max_b)
    else:
        print(max_a)
### BUGGY CODE ###

H, W = map(int, input().split())
X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]
S = [input() for _ in range(H)]
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c==".":
            X[y][x] = X[y][x-1] + 1
    vp = X[y][-1]

    for x in range(W-2, -1, -1):
        v = X[y][x]
        if v != 0:
            v = X[y][x] = max(v, vp)
        vp = v

for x in range(W):
    for y in range(H):
        c = S[y][x]
        if c==".":
            Y[y][x] = Y[y-1][x] + 1

    vp = Y[-1][x]
    for y in range(H-2, -1, -1):
        v = Y[y][x]
        if v != 0:
            v = Y[y][x] = max(v, vp)
        vp = v

ans = 0
for x, y in zip(X, Y):
    for xx, yy in zip(x, y):
        ans = max(ans, xx+yy)
print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]
S = [input() for _ in range(H)]
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c==".":
            X[y][x] = X[y][x-1] + 1
    vp = X[y][-1]

    for x in range(W-2, -1, -1):
        v = X[y][x]
        if v != 0:
            v = X[y][x] = max(v, vp)
        vp = v

for x in range(W):
    for y in range(H):
        c = S[y][x]
        if c==".":
            Y[y][x] = Y[y-1][x] + 1

    vp = Y[-1][x]
    for y in range(H-2, -1, -1):
        v = Y[y][x]
        if v != 0:
            v = Y[y][x] = max(v, vp)
        vp = v

ans = 0
for x, y in zip(X, Y):
    for xx, yy in zip(x, y):
        ans = max(ans, xx+yy)
print(ans-1)
### BUGGY CODE ###

n = int(input())
na = []
for i in range(n):
    a = int(input())
    if a in na:
        na.remove(a)
    else:
        na.append(a)
print(len(na))

### FIXED CODE ###

import collections
n = int(input())
na = []
count = 0
for i in range(n):
    a = int(input())
    na.append(a)
ans = collections.Counter(na)
for j in ans.values():
    if j % 2 == 1:
        count += 1
print(count)
### BUGGY CODE ###

n,k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [10**9]*n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i], dp[j] + abs(h_list[i]-h_list[j]))
print(dp[-1])

### FIXED CODE ###

n,k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [10**9]*n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i], dp[j] + abs(h_list[i]-h_list[j]))
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N,K = map(int, input().split())
MOD = 10**9+7
A = N-K+1

nCr = {}
def cmb(n, r):
    if n < r:
        return 0
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n,r) in nCr:
        return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in range(K):
    print(cmb(K-1, i) * cmb(A, i+1) % MOD)


### FIXED CODE ###

#import sys
#sys.setrecursionlimit(100000)

N,K = map(int, input().split())
MOD = 10**9+7
A = N - K + 1

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(K):
    if N - K - i >= 0:
        print(cmb(K-1, i) * cmb(A, i+1) % MOD)
    else:
        print(0)
### BUGGY CODE ###

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

arr = list(str(S))
ans = []

for i in range(N):
  for j in range(N - i -1):
    for k in range(N - i - j - 2):
      
      a = int(arr[i])
      b = int(arr[j+i+1])
      c = int(arr[k+j+i+2])
      d = 100*a + 10*b + c
      
      if ans.count(d) == 0:
        ans.append(d)
      
      
a =len(ans)
print(a)

### FIXED CODE ###

import math

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

arr = list(str(S))
cnt = 0

for i in range(1000):
  a = math.floor(i/100)
  b = math.floor((i-a*100)/10)
  c = i-a*100-b*10
  
  if str(a) in arr:
    an = arr.index(str(a))
    del arr[:an+1]
    
    if str(b) in arr:
      bn = arr.index(str(b))
      del arr[:bn+1]
      
      if str(c) in arr:
        cnt = cnt + 1
        
  arr = list(str(S))
      
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

for i in range(1, m + 1):
    cm = -1
    cmi = -1
    for j in range(len(xys)):
        if xys[j][0] <= i and xys[j][1] > cm:
            cm = xys[j][1]
            cmi = j
    if cmi >= 0:
        ans += cm
        xys.pop(cmi)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

j = 0
h = []
for i in range(1, m + 1):
    while j < len(xys) and xys[j][0] <= i:
        heappush(h, -xys[j][1])
        j += 1
    if h:
        x = -heappop(h)
        # print("Pick", x)
        ans += x

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

s = list(input())
t = list(input())

arr = [[s[i],t[i]] for i in range(len(s))]

ans = 'Yes'

for j in range(len(s)):
    if s.count(s[j]) != t.count(t[j]) or s.count(s[j]) != arr.count(arr[j]):
        ans = 'No'

print(ans)


### FIXED CODE ###

s = input()
t = input()

counta={}
countb={}

for i in s:
    if i in counta:
        counta[i] += 1
    else:
        counta[i] = 1

for y in t:
    if y in countb:
        countb[y] += 1
    else:
        countb[y] = 1

if sorted(counta.values())  == sorted(countb.values()):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N,K,Q=map(int,input().split()) #Nは人の人数、Kはみなが最初に持っているポイント、Qはクイズの回数
L=[K]*N
for i in range(Q):
  m=int(input())-1
  for j in range(N):
    if j!=m:
      L[j]-=1
for k in range(N):
  if L[k]>0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

N,K,Q=map(int,input().split()) #Nは人の人数、Kはみなが最初に持っているポイント、Qはクイズの回数
L=[K-Q]*N #
for i in range(Q):
    m=int(input())-1
    L[m]+=1
for k in range(N):
    if L[k]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    cur = [[0]*4 for _ in range(C+1)]
    prev = [[0]*4 for _ in range(C+1)]

    for i in range(R):
        cur, prev = prev, cur
        for j in range(C):
            for k in range(4): cur[j+1][k] = cur[j][k]
            v = max(prev[j+1])
            cur[j+1][0] = max(cur[j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                cur[j+1][1] = max(cur[j+1][1], cur[j][0] + u,  v + u)
                cur[j+1][2] = max(cur[j+1][2], cur[j][1] + u )
                cur[j+1][3] = max(cur[j+1][3], cur[j][2] + u )
        # print(cur)

    return max(cur[C])

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

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

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = [int(i) for i in A.split()]
B = [int(i) for i in B.split()]
C = [int(i) for i in C.split()]
Ans = [0 for i in range(K)]
for a in A:
    for b in B:
        for c in C:
            abc = a+b+c
            if min(Ans) < a + b + c:
                Ans[Ans.index(min(Ans))] = a+b+c
Ans = sorted(Ans,reverse=True)
for i in range(len(Ans)):
    print(Ans[i])

### FIXED CODE ###

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = sorted([int(i) for i in A.split()],reverse=True)[:K]
B = sorted([int(i) for i in B.split()],reverse=True)[:K]
C = sorted([int(i) for i in C.split()],reverse=True)[:K]

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 9876598765

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k]+dist[k][j])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)
### BUGGY CODE ###

K, S = map(int, input().split())

count = 0
for x in range(K+1):
    if S-x<=2*K:
        for y in range(K+1):
            if S-x-y<=K:
                for z in range(K+1):
                    if x+y+z==S:
                        count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())

count = 0
for x in range(K+1):
    if S-x<=2*K and S-x>=0:
        for y in range(K+1):
            if S-x-y<=K and S-x-y>=0:
                count += 1
#                 for z in range(K+1):
#                     if x+y+z==S:
#                         count += 1
print(count)
### BUGGY CODE ###

N,K=input().split()
N,K=[int(N),int(K)]

if N%K==0:
  print(0)
else:
  minimum=N
  N=abs(N-K)

  if minimum <=N:
      print(minimum)
  else:
      while minimum > N:
          minimum=N
          N=abs(N-K)
      print(minimum)

### FIXED CODE ###

N,K=input().split()
N,K=[int(N),int(K)]

minimum=N%K
while N%K>K-N%K:
    minimum=K-N%K
    N=K-N%K
print(minimum)
### BUGGY CODE ###

n = int(input())
right = 0
left = n - 1
print(right)
prev = input()
if prev == 'Vacant':
    exit()
v = pow(2, math.floor(math.log(n, 2)))
middle = right + v
for i in range(19):
    print(middle)
    status = input()
    v = v // 2
    if status == 'Vacant':
        exit()
    elif status == prev:
        right = middle
        middle = right + v
    else:
        left = middle
        middle = left - v
    prev = status

### FIXED CODE ###

n = int(input())
left = 0
right = n - 1
print(left)
first = input()
second = 'Male' if first == 'Female' else 'Female'
p = 0
while True:
    p = (left + right) // 2
    print(p)
    status = input()
    if status == 'Vacant':
        break
    if p % 2 == 0:
        if status == first:
            left = p + 1
        else:
            right = p
    else:
        if status == second:
            left = p + 1
        else:
            right = p
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

root = {}
for i in range(n-1):
    a, b = map(int, input().split())
    if a in root:
        root[a] += [b]
    else:
        root.setdefault(a, [b])
    if b in root:
        root[b] += [a]
    else:
        root.setdefault(b, [a])
    
cnt = [0 for _ in range(n+1)]
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

quu = [1]
visited = []
while len(quu) > 0:
    now = quu.pop(0)
    visited += [now]
    child = root[now]
    for i in range(len(child)):
        if not child[i] in visited:
            quu += [child[i]]
            cnt[child[i]] += cnt[now]

print(" ".join(map(str, cnt[1:])))

### FIXED CODE ###

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

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

root = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    root[a].append(b)
    root[b].append(a)
    
cnt = [0 for _ in range(n+1)]
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

def rec(node, parent):
    for i in root[node]:
        if i == parent:
            continue
        cnt[i] += cnt[node]
        rec(i, node)

rec(1, 1)
print(" ".join(map(str, cnt[1:])))
### BUGGY CODE ###

import itertools

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

# 2a = xk, 2b = ykのとき a+b = (x+y)k/2
# x+yが偶数、すなわちx,yの偶奇が一致するならばa+bはkの倍数となる。他の組合せでも同様
# a,b,cの候補リストを用意して重複順列計算

abc_list_even = []
abc_list_odd = []

for a in range(1, N+1):
    if (2*a)%K == 0:
        if ((2*a)//K)%2 == 0:
            abc_list_even.append(a)
        else:
            abc_list_odd.append(a)

print(len(list(itertools.product(abc_list_even, repeat=3))) + len(list(itertools.product(abc_list_odd, repeat=3))))

### FIXED CODE ###

import itertools

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

# 2a = xk, 2b = ykのとき a+b = (x+y)k/2
# x+yが偶数、すなわちx,yの偶奇が一致するならばa+bはkの倍数となる。他の組合せでも同様
# a,b,cの候補リストを用意して重複順列計算

abc_list_even = []
abc_list_odd = []

for a in range(1, N+1):
    if (2*a)%K == 0:
        if ((2*a)//K)%2 == 0:
            abc_list_even.append(a)
        else:
            abc_list_odd.append(a)

print(len(abc_list_even)**3 + len(abc_list_odd)**3)
### BUGGY CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()
sa = []
onesam = 2000000000
for i in range(len(xl)-1):
    one_sa = xl[i+1] - xl[i]
    if one_sa % onesam == 0:
        continue
    if onesam > one_sa:
        onesam = one_sa
        sa.append(one_sa)
        
    
sa.sort()
samin = min(sa)

flag = 0
while flag == 0:
    amari = 0
    for i in sa:
        amari += i % samin
        if amari != 0:
            break
            
    if amari == 0:
        flag = 1
        break
    else:
        for j in range(1,samin+1):
            if samin % j == 0:
                samin = samin // j
                break
print(samin)
        

### FIXED CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()

onesam = 0

if len(xl) == 1:
    print(abs(xl[0] - x))
    exit()

for i in range(len(xl)-1):
    one_sa = xl[i+1] - xl[i]
    if onesam == 0:
        onesam = abs(one_sa)
    else:
        short,big = min(onesam,one_sa),max(onesam,one_sa)
        if big % short == 0:
            onesam = short
            continue
        else:
            while big % short != 0:
                short = short -1
#                 for k in range(2,short+1):
#                     if short % k == 0:
#                         short = short // k
#                         break
            onesam = short
            
print(onesam)
### BUGGY CODE ###

S = input()
L = len(S)

INF = float('inf')
dp = [[INF]*2 for _ in range(L)]
dp[0][0] = int(S[-1])
dp[0][1] = 10-int(S[-1])
S = S[::-1]
for i,c in enumerate(S[1:]):
    c = int(c)
    d = 10-c
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+c)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0]+d)
    c += 1
    d -= 1
    if c==10:
        dp[i+1][1] = min(dp[i+1][1], dp[i][1])
    else:
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+c)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+d)
print(min(dp[-1][0], dp[-1][1]+1))

### FIXED CODE ###

S = input()
L = len(S)

INF = float('inf')
dp = [[INF]*2 for _ in range(L)]
dp[0][0] = int(S[-1])
dp[0][1] = 10-int(S[-1])
S = S[::-1]
for i,c in enumerate(S[1:]):
    c = int(c)
    d = 10-c
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+c)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0]+d)
    c += 1
    d -= 1
    if c==10:
        dp[i+1][1] = min(dp[i+1][1], dp[i][1])
    else:
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+c)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+d)
print(min(dp[-1][0], dp[-1][1]+1))
### BUGGY CODE ###

s = input()
Q = int(input())
for q in range(Q):
    query = input()
    if query[0] == '1':
        s = s[::-1]
    else:
        if query[2] == '1':
            s = query[-1] + s
        else:
            s += query[-1]

print(s)


### FIXED CODE ###

from queue import deque

s = deque([i for i in input()])
Q = int(input())
state = 0
for _ in range(Q):
    q = input()
    if q[0] == '1':
        if state == 0:
            state = 1
        else:
            state = 0
    else:
        if int(q[2]) == 1:
            if state == 0:
                s.appendleft(q[-1])
            else:
                s.append(q[-1])
        elif int(q[2]) == 2:
            if state == 0:
                s.append(q[-1])
            else:
                s.appendleft(q[-1])

if state == 1:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

H, N = [int(s) for s in input().split()]
dec = []
cost = []
for i in range(N):
    a, b = [int(s) for s in input().split()]
    dec.append(a)
    cost.append(b)
memo = [None]*(H+1)
memo[0] = 0
for h in range(1,H+1):
    memo[h] = memo[max(0,h-dec[0])]+cost[0]
    for i in range(1,N):
        memo[h] = min(memo[h], memo[max(0,h-dec[i])]+cost[i])
print(memo[H])

### FIXED CODE ###

H, N = [int(s) for s in input().split()]
dec = []
cost = []
for i in range(N):
    a, b = [int(s) for s in input().split()]
    dec.append(a)
    cost.append(b)
bar = ((H-1)//dec[0]+1)*cost[0]
memo = [bar]*(H+1)
memo[0] = 0
for h in range(1,H+1):
    for i in range(N):
        memo[h] = min(memo[h], memo[max(0,h-dec[i])]+cost[i])
print(memo[H])
### BUGGY CODE ###

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

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}
move = [0] * (H*W + 1)

for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    move[i] = abs(a%W - b % W) + abs(a//W - b//W)

memo = [[None] * (H*W+1) for _ in range(H*W+1)]
for l,r in LR:
    if l == r:
        print(0)
        continue
    if memo[l][r]:
        print(memo[l][r])
    else:
        t = sum(move[l+D:r+1:D])
        memo[l][r] = t
        print(t)
    

### FIXED CODE ###

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

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}

memo = [0] * (H*W+1)
for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    memo[i] = memo[i-D] + abs(a%W - b % W) + abs(a//W - b//W)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(memo[r] - memo[l])