k = int(eval(input()))

from collections import deque

dic = {1:1}

queue = deque([[1,1]])

while queue:

    v,cost = queue.popleft()

    v_ = (v+1)%k

    if not v_ in dic or cost+1<dic[v_]:

        dic[v_] = cost+1

        queue.appendleft([v_,cost+1])

    v_ = v*10%k

    if not v_ in dic or cost<dic[v_]:

        dic[v_] = cost

        queue.append([v_,cost])



print((dic[0]))
from collections import deque

K = int(eval(input()))

d={1:1}

q = deque()

q.append([1,1])



while q:

    a,c = q.popleft()

    a_ = (a*10)%K

    if(a_ not in d or c < d[a_]):

        d[a_]=c

        q.appendleft([a_,c])

    b_ = (a+1)%K

    if(b_ not in d or c < d[b_]):

        d[b_] = c+1

        q.append([b_,c+1])



print((d[0]))

    

k = int(eval(input()))
from collections import deque

dic = {1: 1}
queue = deque([[1, 1]])
while queue:
    v, cost = queue.popleft()
    v_ = (v + 1) % k
    if not v_ in dic or cost + 1 < dic[v_]:
        dic[v_] = cost + 1
        queue.appendleft([v_, cost + 1])
    v_ = v * 10 % k
    if not v_ in dic or cost < dic[v_]:
        dic[v_] = cost
        queue.append([v_, cost])
print((dic[0]))

from collections import deque

K = int(eval(input()))
d = {1: 1}
q = deque()
q.append([1, 1])
while q:
    a, c = q.popleft()
    a_ = (a * 10) % K
    if a_ not in d or c < d[a_]:
        d[a_] = c
        q.appendleft([a_, c])
    b_ = (a + 1) % K
    if b_ not in d or c < d[b_]:
        d[b_] = c + 1
        q.append([b_, c + 1])
print((d[0]))

-k = int(eval(input())) -dic = {1: 1} -queue = deque([[1, 1]]) -while queue: -    v, cost = queue.popleft() -    v_ = (v + 1) % k -    if not v_ in dic or cost + 1 < dic[v_]: -        dic[v_] = cost + 1 -        queue.appendleft([v_, cost + 1]) -    v_ = v * 10 % k -    if not v_ in dic or cost < dic[v_]: -        dic[v_] = cost -        queue.append([v_, cost]) -print((dic[0])) +K = int(eval(input())) +d = {1: 1} +q = deque() +q.append([1, 1]) +while q: +    a, c = q.popleft() +    a_ = (a * 10) % K +    if a_ not in d or c < d[a_]: +        d[a_] = c +        q.appendleft([a_, c]) +    b_ = (a + 1) % K +    if b_ not in d or c < d[b_]: +        d[b_] = c + 1 +        q.append([b_, c + 1]) +print((d[0]))