CodeEff/ECCO huggingface dataset:
# Original solution
from math import sqrt, ceil

def_val = 2 ** 31 - 1
n, q = list(map(int, input().split()))
unit = ceil(sqrt(n))

l = [(def_val, [def_val] * unit) for _ in range(unit)]

while q:
    op, s, t = list(map(int, input().split()))
    sd, sm = s // unit, s % unit
    if op:
        td, tm = t // unit, t % unit
        if sd == td:
            print((min(l[sd][1][sm:tm + 1])))
        else:
            unit_min = min((tup[0] for tup in l[sd + 1:td]), default=def_val)
            s_min = min(l[sd][1][sm:], default=def_val)
            t_min = min(l[td][1][:tm + 1], default=def_val)
            print((min(unit_min, s_min, t_min)))
    else:
        unit_list = l[sd][1]
        unit_list[sm] = t
        l[sd] = (min(unit_list), unit_list)
    q -= 1

# Optimized solution
class SegTreeMin:
    def __init__(self, n):
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [(1 << 31) - 1] * (n2 << 1)
        self.output = []

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, s, t):
        self.output.append(self._get_min(s, t + 1, 1, 0, self.n2))

    def _get_min(self, a, b, k, l, r):
        if r <= a or b <= l:
            return (1 << 31) - 1
        if a <= l and r <= b:
            return self.tree[k]
        m = (l + r) // 2
        return min(
            self._get_min(a, b, k << 1, l, m),
            self._get_min(a, b, (k << 1) + 1, m, r))

    def print(self):
        print('\n'.join(map(str, self.output)))


n, q = map(int, input().split())
st = SegTreeMin(n)
fs = [st.update, st.get_min]
for c, x, y in (map(int, input().split()) for _ in range(q)):
    fs[c](x, y)
st.print()
# Original solution
import math
num,query = (int(n) for n in input().split(' '))
table = [2**31 - 1 for n in range(num)]
sqrttable = []
sqrtnum = math.floor(math.sqrt(num))
tempmin = float("inf")
for t in range(num):
    if t % sqrtnum == sqrtnum - 1:
        tempmin = min(table[t],tempmin)
        sqrttable.append(tempmin)
    elif t == num - 1:
        tempmin = min(table[t],tempmin)
        sqrttable.append(tempmin)
    else:
        tempmin = min(table[t],tempmin)

for q in range(query):
    #print(sqrtnum,table,sqrttable)
    temp = [int(n) for n in input().split(' ')]
    if temp[0] == 0:
        table[temp[1]] = temp[2]
        tempmin = float("inf")
        for tm in range(sqrtnum*(temp[1]//sqrtnum),min(num,sqrtnum*(temp[1]//sqrtnum + 1))):
            tempmin = min(table[tm],tempmin)
        sqrttable[temp[1]//sqrtnum] = tempmin
    else:
        tempmin = float("inf")
        if temp[1] % sqrtnum != 0:
            for ini in range(temp[1],min(temp[2]+1,sqrtnum * math.ceil(temp[1] / sqrtnum))):
                tempmin = min(tempmin,table[ini])
        newtemp2 = temp[2] + 1
        for sqt in range(math.ceil(temp[1] / sqrtnum),newtemp2 // sqrtnum):
            tempmin = min(sqrttable[sqt],tempmin)
        if temp[2] % sqrtnum != sqrtnum -1:
            for end in range(max(temp[1],sqrtnum * (temp[2]//sqrtnum)),temp[2]+1):
                tempmin = min(tempmin,table[end])
        #print(tempmin,sqrtnum,temp[1],temp[2],table,sqrttable)
        print(tempmin)

# Optimized solution
import math

def update(index,n):
    targ[index] = n
    index = (index - 1) // 2
    while True:
        targ[index] = min(targ[index * 2 + 1],targ[index * 2 + 2])
        if index <= 0:
            break
        index = (index - 1) // 2

def find(i,e,node,inode,enode):
    #print(i,e,node,inode,enode)
    if inode > e or enode < i:
        return float("inf")
    elif (i <= inode and enode <= e) or inode==enode:
        return targ[node]

    else:
        irange = find(i,e,2*node + 1,inode,(inode+enode)// 2 )
        erange = find(i,e,2*node + 2,(inode+enode)//2 + 1,enode)
        return min(irange,erange)

num,query = (int(n) for n in input().split(' '))
initial = 2147483647
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
global targ
targ = [initial] * (ln + num + tail)

for q in range(query):
    #print(targ)
    temp = [int(n) for n in input().split(' ') ]
    if temp[0] == 0:
        update(temp[1] + ln,temp[2])
    else:
        print((find(temp[1],temp[2],0,0,ln)))
# Original solution
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a == b:
            return self.segtree[self.length - 1 + a]
        elif a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print((rmq.find(i, n, 0, 0, rmq.length - 1)))

# Optimized solution
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print((rmq.find(i, n, 0, 0, rmq.length - 1)))
# Original solution
n, q = list(map(int, input().split()))
default = 2**31 - 1

mindict = {}
answer_stk = []

for i in range(q) :
    query, x, y = list(map(int, input().split()))
    
    if query == 0 :
        mindict[x] = y
    else :
        min_between = default
        for k in list(mindict.keys()) :
            if k >= x and k <= y :
                min_between = min(min_between, mindict[k])
                
        answer_stk.append(min_between)
        
for a in answer_stk :
    print(a)
                
    


# Optimized solution
n, q = list(map(int, input().split()))
answer = []

size = 1
while size < n :
    size *= 2
size = size * 2 - 1

seg_tree = [2**31 -1 for x in range(size)]

def update(i, x) :
    ind = size // 2 + i
    seg_tree[ind] = x
    
    while ind : 
        ind = (ind - 1) // 2
        ch1 = seg_tree[ind * 2 + 1]
        ch2 = seg_tree[ind * 2 + 2]
        seg_tree[ind] = min(ch1, ch2)
        
def find(s, t, k, l, r) :
    # no overlap
    if r < s or t < l :
        return 10 ** 20
    # total overlap
    if s <= l and r <= t :
        return seg_tree[k]
    # partial overlap
    else :
        vl = find(s, t, k * 2 + 1, l, (l + r) // 2)
        vr = find(s, t, k * 2 + 2, (l + r) // 2 + 1, r)
        
        return min(vl, vr)

for i in range(q) :
    com, x, y = list(map(int, input().split()))
    
    if com == 0 :
        update(x, y)
    else :
        answer.append(find(x, y, 0, 0, size // 2))

for a in answer :
    print(a)
# Original solution
from collections import deque
K = int(eval(input()))
G = [[] for i in range(K)]

for n in range(K):
    G[n].append([(n + 1) % K, 1])
    G[n].append([(10 * n) % K, 0])

que = deque([[1, 1]])
dist = [float('inf')] * K

while que:
    node, cost = que.pop()
    dist[node] = min(cost, dist[node])
    for e, e_cost in G[node]:
        if dist[e] != float('inf'):
            continue

        if e_cost == 0:
            que.append([e, cost + 0])

        if e_cost == 1:
            que.appendleft([e, cost + 1])

print((dist[0]))


# Optimized solution
from collections import deque
K = int(eval(input()))
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((10 * i) % K, 0))
    G[i].append(((i + 1) % K, 1))

dist = [float('inf')] * K
dist[1] = 1
que = deque()
que.append(1)

while que:
    n = que.pop()
    for v, c in G[n]:
        if dist[v] > dist[n] + c:
            dist[v] = dist[n] + c
            if c == 0:
                que.append(v)
            else:
                que.appendleft(v)

print((dist[0]))
# Original solution
from collections import deque

K = int(eval(input()))

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
que = deque([s])
dist[s] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w, c in G[v]:
        if d+c < dist[w]:
            dist[w] = d+c
            if c:
                que.append(w)
            else:
                que.appendleft(w)

print((dist[0]+1))

# Optimized solution
from collections import deque

K = int(eval(input()))

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print((dist[0]+1))
# Original solution
from collections import deque

K = int(eval(input()))

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print((dist[0]+1))

# Optimized solution
from collections import deque

K = int(eval(input()))

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print((dist[0]+1))
# Original solution
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = [(1, 0)]
    vis = {}
    while q:
        # print(len(q))
        u, cc = q.pop(0)
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.insert(0, (v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()


# Optimized solution
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = deque()
    q.append((1, 0))

    vis = {}
    while q:
        u, cc = q.popleft()
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.appendleft((v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()
# Original solution
from collections import deque
K = int(eval(input()))

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if (x, y, k) in used:
        continue
    else:
        used.add((x, y, k))
    # print(x, y, k)
    if k % K == 0:
        print(x)
        break
    q.appendleft((x, 0, k*10%K))
    if (y + 1) % 10 == 0:
        q.appendleft((x, 0, k+1))
    else:
        q.append((x+1, y+1, k+1))


# Optimized solution
from collections import deque
K = int(eval(input()))

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if k % K == 0:
        print(x)
        break
    if (x, 0, k*10%K) in used:
        continue
    else:
        used.add((x, 0, k*10%K))
    q.appendleft((x, 0, k*10%K))
    if (y + 1) % 10 == 0:
        q.appendleft((x, 0, k+1))
    else:
        q.append((x+1, y+1, k+1))
# Original solution
#!/usr/bin/env python3
from collections import deque

INF = 10**9
k = int(eval(input()))

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print((dist[0] + 1))

# Optimized solution
from collections import*
q=deque([(1,1)])
k=int(eval(input()))
m={}
while q:
 n,s=q.pop()
 if(n in m)-1:m[n]=s;q+=(n*10%k,s),;q.appendleft((-~n%k,s+1))
print((m[0]))
# Original solution
from collections import*
q=[(1,1)]
k=int(eval(input()))
m={}
while q:
 n,s=q.pop()
 if(n in m)-1:m[n]=s;q+=(n*10%k,s),;q=[(-~n%k,s+1)]+q
print((m[0]))

# Optimized solution
#!/usr/bin/env python3
from collections import deque

INF = 10**9
k = int(eval(input()))

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print((dist[0] + 1))
# Original solution
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(eval(input()))

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

distances = [INF for _ in range(K)]

# 01BFS
remains = deque()
remains.append((1, 1))
while distances[0] == INF:
    d, mod_k = remains.popleft()
    distances[mod_k] = d
    if distances[(mod_k + 1) % K] == INF:
        remains.append((d + 1, (mod_k + 1) % K))
    if distances[mod_k * 10 % K] == INF:
        remains.appendleft((d, mod_k * 10 % K))
print((distances[0]))


# Optimized solution
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(eval(input()))

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

distances = [INF for _ in range(K)]

# 01BFS
distances[1] = 1
remains = deque()
remains.append((1, 1))
while True:
    d, mod_k = remains.popleft()
    if mod_k == 0:
        break
    if d + 1 < distances[(mod_k + 1) % K]:
        distances[(mod_k + 1) % K] = d + 1
        remains.append((d + 1, (mod_k + 1) % K))
    if d < distances[mod_k * 10 % K]:
        distances[mod_k * 10 % K] = d
        remains.appendleft((d, mod_k * 10 % K))
print((distances[0]))
# Original solution
n = eval(input())


def get_sum(n):
    s = str(n)
    arr = list(map(int, list(s)))
    return sum(arr)

ans = get_sum(n)
i = 1
for i in range(1, 10000):
    m = get_sum(n * i)
    if ans > m:
        ans = m

print(ans)


# Optimized solution
import collections


def ans(n):
    dist = [10 ** 5] * n
    dist[1] = 1
    d = collections.deque()
    d.append(1)
    while not d.count == 0:
        u = d.popleft()
        if u == 0:
            return dist[u]
        if dist[u] < dist[(u * 10) % n]:
            dist[(u * 10) % n] = dist[u]
            d.appendleft((u * 10) % n)
        if dist[u] < dist[(u + 1) % n]:
            dist[(u + 1) % n] = dist[u] + 1
            d.append((u + 1) % n)

n = int(eval(input()))
print((ans(n)))
# Original solution
import sys
# import math
# import queue
# import copy
# import bisect#2分探索


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(eval(input()))

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print((vs+1)) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


# Optimized solution
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(eval(input()))

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print((vs+1)) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
def resolve():
    k=int(eval(input()))
    E=[[] for _ in range(k)]
    for i in range(k):
        E[i].append(((i+1)%k,1))
        E[i].append(((10*i)%k,0))

    # 0-1 BFS
    dist=[INF]*k
    dist[1]=0
    Q=deque([1])
    while(Q):
        v=Q.popleft()
        for nv,w in E[v]:
            if(dist[nv]<=dist[v]+w): continue
            dist[nv]=dist[v]+w
            if(w==0): Q.appendleft(nv)
            else: Q.append(nv)
    print((dist[0]+1))
resolve()

# Optimized solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    k = int(eval(input()))
    dist = [INF] * k
    dist[1] = 1
    queue = deque([1])

    while queue:
        v = queue.pop()
        if dist[10 * v % k] > dist[v]:
            dist[10 * v % k] = dist[v]
            queue.appendleft(10 * v % k)
        if dist[(v + 1) % k] > dist[v] + 1:
            dist[(v + 1) % k] = dist[v] + 1
            queue.append((v + 1) % k)

    print((dist[0]))
resolve()
# Original solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    k = int(eval(input()))
    dist = [INF] * k
    dist[1] = 1
    queue = deque([1])

    while queue:
        v = queue.pop()
        if dist[10 * v % k] > dist[v]:
            dist[10 * v % k] = dist[v]
            queue.appendleft(10 * v % k)
        if dist[(v + 1) % k] > dist[v] + 1:
            dist[(v + 1) % k] = dist[v] + 1
            queue.append((v + 1) % k)

    print((dist[0]))
resolve()

# Optimized solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k = int(eval(input()))
    dist = [INF] * k
    dist[1] = 1
    queue = [1]

    for v in queue:
        tmp = [v]
        for v in tmp:
            if dist[10 * v % k] > dist[v]:
                dist[10 * v % k] = dist[v]
                tmp.append(10 * v % k)
            if dist[(v + 1) % k] > dist[v] + 1:
                dist[(v + 1) % k] = dist[v] + 1
                queue.append((v + 1) % k)

    print((dist[0]))
resolve()
# Original solution
k = int(eval(input()))

a = [0]*(10**6)
for i in range(10**6):
    a[i] = sum([int(c) for c in str(k*(i+1))])

print((min(a)))


# Optimized solution
from collections import deque
k = int(eval(input()))
d = deque()
mat = []
for i in range(k):
    mat.append([])
#mark = [False]*k
dis = [10**18]*k
dis[1] = 0
for i in range(k):
    mat[i].append(((i+1)%k,True))

    if (10*i)%k != i:
        mat[i].append(((10*i)%k,False))

#bfs 1->0
d.append(1)
res = 0
while d:
    left = d.popleft()
    for neighbour,edge in mat[left]:
        distance = edge + dis[left]
        if dis[neighbour] > distance: 
            dis[neighbour] = distance 
            
            if edge == 0:
                d.appendleft(neighbour)
            else:
                d.append(neighbour)
print((dis[0]+1))