from heapq import heappush, heappop

k = int(eval(input()))



heap = [(1,1)]

dist = [float("inf")]*k

while heap:

    cost, cur = heappop(heap)

    if dist[cur] <= cost:

        continue

    dist[cur] = cost

    # +1

    nxt = (cur+1)%k

    heappush(heap, (cost+1, nxt))

    # *10

    nxt = cur*10 % k

    heappush(heap, (cost, nxt))



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

k = int(eval(input()))



que = deque()

que.append((1,1))

dist = [float("inf")]*k

while que:

    cost, cur = que.popleft()

    if dist[cur] <= cost:

        continue

    dist[cur] = cost

    # +1

    nxt = (cur+1)%k

    que.append((cost+1,nxt))

    # *10

    nxt = cur*10 % k

    que.appendleft((cost, nxt))

print((dist[0]))
from heapq import heappush, heappop

k = int(eval(input()))
heap = [(1, 1)]
dist = [float("inf")] * k
while heap:
    cost, cur = heappop(heap)
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    # +1
    nxt = (cur + 1) % k
    heappush(heap, (cost + 1, nxt))
    # *10
    nxt = cur * 10 % k
    heappush(heap, (cost, nxt))
print((dist[0]))

from collections import deque

k = int(eval(input()))
que = deque()
que.append((1, 1))
dist = [float("inf")] * k
while que:
    cost, cur = que.popleft()
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    # +1
    nxt = (cur + 1) % k
    que.append((cost + 1, nxt))
    # *10
    nxt = cur * 10 % k
    que.appendleft((cost, nxt))
print((dist[0]))

-from heapq import heappush, heappop +from collections import deque -heap = [(1, 1)] +que = deque() +que.append((1, 1)) -while heap: -    cost, cur = heappop(heap) +while que: +    cost, cur = que.popleft() -    heappush(heap, (cost + 1, nxt)) +    que.append((cost + 1, nxt)) -    heappush(heap, (cost, nxt)) +    que.appendleft((cost, nxt))