from collections import deque



K = int(eval(input()))

D = [-1]*K

Q = deque()

Q.append([1,0])

while D[0] == -1:

    k,v = Q.popleft()

    D[k] = v

    j = (k*10)%K

    if D[j] == -1:

        Q.appendleft([j,v])

    l = (k+1)%K

    if D[l] == -1:

        Q.append([l,v+1])



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



K = int(eval(input()))

D = [9999]*K

D[1] = 1

H = deque()

H.append(1)

while len(H) != 0:

    h = H.pop()

    if D[(h*10)%K] > D[h]:

        D[(h*10)%K] = D[h]

        H.append((h*10)%K)

    if D[(h+1)%K] > D[h] + 1:

        D[(h+1)%K] = D[h] + 1

        H.appendleft((h+1)%K)



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

K = int(eval(input()))
D = [-1] * K
Q = deque()
Q.append([1, 0])
while D[0] == -1:
    k, v = Q.popleft()
    D[k] = v
    j = (k * 10) % K
    if D[j] == -1:
        Q.appendleft([j, v])
    l = (k + 1) % K
    if D[l] == -1:
        Q.append([l, v + 1])
print((D[0] + 1))

from collections import deque

K = int(eval(input()))
D = [9999] * K
D[1] = 1
H = deque()
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h * 10) % K] > D[h]:
        D[(h * 10) % K] = D[h]
        H.append((h * 10) % K)
    if D[(h + 1) % K] > D[h] + 1:
        D[(h + 1) % K] = D[h] + 1
        H.appendleft((h + 1) % K)
print((D[0]))

-D = [-1] * K -Q = deque() -Q.append([1, 0]) -while D[0] == -1: -    k, v = Q.popleft() -    D[k] = v -    j = (k * 10) % K -    if D[j] == -1: -        Q.appendleft([j, v]) -    l = (k + 1) % K -    if D[l] == -1: -        Q.append([l, v + 1]) -print((D[0] + 1)) +D = [9999] * K +D[1] = 1 +H = deque() +H.append(1) +while len(H) != 0: +    h = H.pop() +    if D[(h * 10) % K] > D[h]: +        D[(h * 10) % K] = D[h] +        H.append((h * 10) % K) +    if D[(h + 1) % K] > D[h] + 1: +        D[(h + 1) % K] = D[h] + 1 +        H.appendleft((h + 1) % K) +print((D[0]))