#!/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))
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]))
#!/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))

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]))

-#!/usr/bin/env python3 -from collections import deque +from collections import * -INF = 10**9 +q = deque([(1, 1)]) -# (辺の伸びる先, コスト) -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)) +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]))