from heapq import heappush,heappop

K=int(eval(input()))

table=[[] for i in range(K)]

for i in range(K):

    table[i].append([1,(i+1)%K])

    t = (10*i)%K

    if t!=i:

        table[i].append([0,t])

dij=[]

visit=[False]*K

val=[10**9]*K

val[1]=0

heappush(dij,[0,1])

while dij:

    d,x=heappop(dij)

    if val[x]<d:

        continue

    for q,y in table[x]:

        if val[y]>val[x]+q:

            val[y]=val[x]+q

            heappush(dij,[val[y],y])

print((val[0]+1))
from collections import deque

K=int(eval(input()))

table=[[] for i in range(K)]

for i in range(K):

    table[i].append([1,(i+1)%K])

    t = (10*i)%K

    if t!=i:

        table[i].append([0,t])

dij=deque()

visit=[False]*K

val=[10**9]*K

val[1]=0

dij.append([0,1])

while dij:

    d,x=dij.popleft()

    if val[x]<d:

        continue

    for q,y in table[x]:

        if val[y]>val[x]+q:

            val[y]=val[x]+q

            if q==1:

                dij.append([val[y],y])

            else:

                dij.appendleft([val[y],y])

print((val[0]+1))
from heapq import heappush, heappop

K = int(eval(input()))
table = [[] for i in range(K)]
for i in range(K):
    table[i].append([1, (i + 1) % K])
    t = (10 * i) % K
    if t != i:
        table[i].append([0, t])
dij = []
visit = [False] * K
val = [10**9] * K
val[1] = 0
heappush(dij, [0, 1])
while dij:
    d, x = heappop(dij)
    if val[x] < d:
        continue
    for q, y in table[x]:
        if val[y] > val[x] + q:
            val[y] = val[x] + q
            heappush(dij, [val[y], y])
print((val[0] + 1))

from collections import deque

K = int(eval(input()))
table = [[] for i in range(K)]
for i in range(K):
    table[i].append([1, (i + 1) % K])
    t = (10 * i) % K
    if t != i:
        table[i].append([0, t])
dij = deque()
visit = [False] * K
val = [10**9] * K
val[1] = 0
dij.append([0, 1])
while dij:
    d, x = dij.popleft()
    if val[x] < d:
        continue
    for q, y in table[x]:
        if val[y] > val[x] + q:
            val[y] = val[x] + q
            if q == 1:
                dij.append([val[y], y])
            else:
                dij.appendleft([val[y], y])
print((val[0] + 1))

-from heapq import heappush, heappop +from collections import deque -dij = [] +dij = deque() -heappush(dij, [0, 1]) +dij.append([0, 1]) -    d, x = heappop(dij) +    d, x = dij.popleft() -            heappush(dij, [val[y], y]) +            if q == 1: +                dij.append([val[y], y]) +            else: +                dij.appendleft([val[y], y])