# coding: utf-8

# Your code here!



import sys

sys.setrecursionlimit(10**6)

readline = sys.stdin.readline #文字列入力のときは注意



k = int(eval(input()))



g = [[] for _ in range(k)]

for i in range(k):

    g[i].append(((i+1)%k,1))

    if i: g[i].append((10*i%k,0))

#print(g)



from collections import deque

q = deque([(1,1)])

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

res[1] = 1

while q:

    dd,v = q.popleft()

    if res[v] < dd: continue

    if v==0: break

    for c,d in g[v]:

        if res[c] <= res[v] + d: continue

        res[c] = res[v] + d

        if d: q.append((res[c],c))

        else: q.appendleft((res[c],c))



print((res[0]))





# coding: utf-8

# Your code here!

import sys

read = sys.stdin.read

readline = sys.stdin.readline



k, = list(map(int, readline().split()))



from collections import deque

INF = 1<<30

res = [INF]*k

res[1] = 1



q = deque([(1,1)])

while q:

    dv,v = q.popleft()

    if res[v] < dv: continue

    #if v==goal: break

    for to,cost in [(10*v%k,0),((v+1)%k,1)]:

        #print(to,cost)

        if dv + cost < res[to]:

            res[to] = dv + cost

            if cost: q.append((res[to],to))

            else: q.appendleft((res[to],to))

    #print(res)

    

print((res[0]))



# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline  # 文字列入力のときは注意
k = int(eval(input()))
g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i + 1) % k, 1))
    if i:
        g[i].append((10 * i % k, 0))
# print(g)
from collections import deque

q = deque([(1, 1)])
res = [float("inf")] * k
res[1] = 1
while q:
    dd, v = q.popleft()
    if res[v] < dd:
        continue
    if v == 0:
        break
    for c, d in g[v]:
        if res[c] <= res[v] + d:
            continue
        res[c] = res[v] + d
        if d:
            q.append((res[c], c))
        else:
            q.appendleft((res[c], c))
print((res[0]))

# coding: utf-8
# Your code here!
import sys

read = sys.stdin.read
readline = sys.stdin.readline
(k,) = list(map(int, readline().split()))
from collections import deque

INF = 1 << 30
res = [INF] * k
res[1] = 1
q = deque([(1, 1)])
while q:
    dv, v = q.popleft()
    if res[v] < dv:
        continue
    # if v==goal: break
    for to, cost in [(10 * v % k, 0), ((v + 1) % k, 1)]:
        # print(to,cost)
        if dv + cost < res[to]:
            res[to] = dv + cost
            if cost:
                q.append((res[to], to))
            else:
                q.appendleft((res[to], to))
    # print(res)
print((res[0]))

-sys.setrecursionlimit(10**6) -readline = sys.stdin.readline  # 文字列入力のときは注意 -k = int(eval(input())) -g = [[] for _ in range(k)] -for i in range(k): -    g[i].append(((i + 1) % k, 1)) -    if i: -        g[i].append((10 * i % k, 0)) -# print(g) +read = sys.stdin.read +readline = sys.stdin.readline +(k,) = list(map(int, readline().split())) +INF = 1 << 30 +res = [INF] * k +res[1] = 1 -res = [float("inf")] * k -res[1] = 1 -    dd, v = q.popleft() -    if res[v] < dd: +    dv, v = q.popleft() +    if res[v] < dv: -    if v == 0: -        break -    for c, d in g[v]: -        if res[c] <= res[v] + d: -            continue -        res[c] = res[v] + d -        if d: -            q.append((res[c], c)) -        else: -            q.appendleft((res[c], c)) +    # if v==goal: break +    for to, cost in [(10 * v % k, 0), ((v + 1) % k, 1)]: +        # print(to,cost) +        if dv + cost < res[to]: +            res[to] = dv + cost +            if cost: +                q.append((res[to], to)) +            else: +                q.appendleft((res[to], to)) +    # print(res)