import heapq

K=int(eval(input()))

dist=[10**15 for i in range(K)]

dist[1]=1

q=[]

heapq.heappush(q,(0,1))

while (len(q)!=0):

    prc,src=heapq.heappop(q)

    if dist[src]<prc:

        continue

    if dist[(src+1)%K]>dist[src]+1:

        dist[(src+1)%K]=dist[src]+1

        heapq.heappush(q,(dist[(src+1)%K],(src+1)%K))

    if dist[(10*src)%K]>dist[src]:

        dist[(10*src)%K]=dist[src]

        heapq.heappush(q,(dist[(src*10)%K],(src*10)%K))

print((dist[0]))

from collections import deque

K=int(eval(input()))

dist=[10**15 for i in range(K)]

dist[1]=1

q=deque([1])

while(len(q)>0):

    r=q.popleft()

    s=(r+1)%K

    if dist[r]+1<dist[s]:

        dist[s]=dist[r]+1

        q.append(s)

    t=(r*10)%K

    if dist[r]<dist[t]:

        dist[t]=dist[r]

        q.appendleft(t)

print((dist[0]))

import heapq

K = int(eval(input()))
dist = [10**15 for i in range(K)]
dist[1] = 1
q = []
heapq.heappush(q, (0, 1))
while len(q) != 0:
    prc, src = heapq.heappop(q)
    if dist[src] < prc:
        continue
    if dist[(src + 1) % K] > dist[src] + 1:
        dist[(src + 1) % K] = dist[src] + 1
        heapq.heappush(q, (dist[(src + 1) % K], (src + 1) % K))
    if dist[(10 * src) % K] > dist[src]:
        dist[(10 * src) % K] = dist[src]
        heapq.heappush(q, (dist[(src * 10) % K], (src * 10) % K))
print((dist[0]))

from collections import deque

K = int(eval(input()))
dist = [10**15 for i in range(K)]
dist[1] = 1
q = deque([1])
while len(q) > 0:
    r = q.popleft()
    s = (r + 1) % K
    if dist[r] + 1 < dist[s]:
        dist[s] = dist[r] + 1
        q.append(s)
    t = (r * 10) % K
    if dist[r] < dist[t]:
        dist[t] = dist[r]
        q.appendleft(t)
print((dist[0]))

-import heapq +from collections import deque -q = [] -heapq.heappush(q, (0, 1)) -while len(q) != 0: -    prc, src = heapq.heappop(q) -    if dist[src] < prc: -        continue -    if dist[(src + 1) % K] > dist[src] + 1: -        dist[(src + 1) % K] = dist[src] + 1 -        heapq.heappush(q, (dist[(src + 1) % K], (src + 1) % K)) -    if dist[(10 * src) % K] > dist[src]: -        dist[(10 * src) % K] = dist[src] -        heapq.heappush(q, (dist[(src * 10) % K], (src * 10) % K)) +q = deque([1]) +while len(q) > 0: +    r = q.popleft() +    s = (r + 1) % K +    if dist[r] + 1 < dist[s]: +        dist[s] = dist[r] + 1 +        q.append(s) +    t = (r * 10) % K +    if dist[r] < dist[t]: +        dist[t] = dist[r] +        q.appendleft(t)