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

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

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

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

-for n in range(K): -    G[n].append([(n + 1) % K, 1]) -    G[n].append([(10 * n) % K, 0]) -que = deque([[1, 1]]) +for i in range(K): +    G[i].append(((10 * i) % K, 0)) +    G[i].append(((i + 1) % K, 1)) +dist[1] = 1 +que = deque() +que.append(1) -    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]) +    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)