k = int(eval(input()))

from collections import deque

dic = {1:1}

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

while queue:

    v,cost = queue.popleft()

    if not (v+1)%k in dic or cost+1<dic[(v+1)%k]:

        dic[(v+1)%k] = cost+1

        queue.appendleft([(v+1)%k,cost+1])

    if not v*10%k in dic or cost<dic[v*10%k]:

        dic[v*10%k] = cost

        queue.append([v*10%k,cost])



print((dic[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]))
k = int(eval(input()))
from collections import deque

dic = {1: 1}
queue = deque([[1, 1]])
while queue:
    v, cost = queue.popleft()
    if not (v + 1) % k in dic or cost + 1 < dic[(v + 1) % k]:
        dic[(v + 1) % k] = cost + 1
        queue.appendleft([(v + 1) % k, cost + 1])
    if not v * 10 % k in dic or cost < dic[v * 10 % k]:
        dic[v * 10 % k] = cost
        queue.append([v * 10 % k, cost])
print((dic[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]))

-    if not (v + 1) % k in dic or cost + 1 < dic[(v + 1) % k]: -        dic[(v + 1) % k] = cost + 1 -        queue.appendleft([(v + 1) % k, cost + 1]) -    if not v * 10 % k in dic or cost < dic[v * 10 % k]: -        dic[v * 10 % k] = cost -        queue.append([v * 10 % k, cost]) +    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])