# 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])

INF = float("inf")

res = [INF]*k

res[1] = 1

while q and res[0] == INF:

#    print(q)

    v = q.popleft()

    for c,d in g[v]:

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

        res[c] = res[v] + d

        if d: q.append(c)

        else: q.appendleft(c)



#print(res)

#print(used)

print(res[0])

"""



from heapq import *

def dijkstra(g,start):

    n = len(g)

    dist = [float("inf")]*(n) #startからの最短距離

    pending = n-1 #未確定の点の個数

    dist[start] = 0

    q = [(0,start)] #(そこまでの距離、点)

    while q and pending:

        c,v = heappop(q)

        if dist[v] < c: continue

        pending -= 1

        for to, cost in g[v]:

            if dist[v] + cost < dist[to]:

                dist[to] = dist[v] + cost

                heappush(q, (dist[to], to))

    return dist



dist = dijkstra(g,1)

print((dist[0]+1))









# coding: utf-8

# Your code here!



"""

01-BFS

辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる

"""

from collections import deque

def bfs01(g,start):

    n = len(g)

    res = [float("inf")]*n #startからの最短距離

    res[start] = 0

    pending = n-1 #未確定の点の個数

    q = deque([(0,start)]) #(そこまでの距離、点)

    while q and pending:

        dv,v = q.popleft()

        if res[v] < dv: continue

        pending -= 1

        #if v==goal: break

        for to,cost in g[v]:

            if dv + cost < res[to]:

                res[to] = dv + cost

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

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

    return res



######################################################################

#ARC084 small multiple

#

######################################################################



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))

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



res = bfs01(g,1)

print((res[0]+1))

# 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])
INF = float("inf")
res = [INF]*k
res[1] = 1
while q and res[0] == INF:
#    print(q)
    v = q.popleft()
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append(c)
        else: q.appendleft(c)
#print(res)
#print(used)
print(res[0])
"""
from heapq import *


def dijkstra(g, start):
    n = len(g)
    dist = [float("inf")] * (n)  # startからの最短距離
    pending = n - 1  # 未確定の点の個数
    dist[start] = 0
    q = [(0, start)]  # (そこまでの距離、点)
    while q and pending:
        c, v = heappop(q)
        if dist[v] < c:
            continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist


dist = dijkstra(g, 1)
print((dist[0] + 1))

# coding: utf-8
# Your code here!
"""
01-BFS
辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる
"""
from collections import deque


def bfs01(g, start):
    n = len(g)
    res = [float("inf")] * n  # startからの最短距離
    res[start] = 0
    pending = n - 1  # 未確定の点の個数
    q = deque([(0, start)])  # (そこまでの距離、点)
    while q and pending:
        dv, v = q.popleft()
        if res[v] < dv:
            continue
        pending -= 1
        # if v==goal: break
        for to, cost in g[v]:
            if dv + cost < res[to]:
                res[to] = dv + cost
                if cost:
                    q.append((res[to], to))
                else:
                    q.appendleft((res[to], to))
    return res


######################################################################
# ARC084 small multiple
#
######################################################################
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))
    g[i].append((10 * i % k, 0))
res = bfs01(g, 1)
print((res[0] + 1))

+""" +01-BFS +辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる +""" +from collections import deque + + +def bfs01(g, start): +    n = len(g) +    res = [float("inf")] * n  # startからの最短距離 +    res[start] = 0 +    pending = n - 1  # 未確定の点の個数 +    q = deque([(0, start)])  # (そこまでの距離、点) +    while q and pending: +        dv, v = q.popleft() +        if res[v] < dv: +            continue +        pending -= 1 +        # if v==goal: break +        for to, cost in g[v]: +            if dv + cost < res[to]: +                res[to] = dv + cost +                if cost: +                    q.append((res[to], to)) +                else: +                    q.appendleft((res[to], to)) +    return res + + +###################################################################### +# ARC084 small multiple +# +###################################################################### -    if i: -        g[i].append((10 * i % k, 0)) -# print(g) -""" -from collections import deque -q = deque([1]) -INF = float("inf") -res = [INF]*k -res[1] = 1 -while q and res[0] == INF: -#    print(q) -    v = q.popleft() -    for c,d in g[v]: -        if res[c] <= res[v] + d: continue -        res[c] = res[v] + d -        if d: q.append(c) -        else: q.appendleft(c) -#print(res) -#print(used) -print(res[0]) -""" -from heapq import * - - -def dijkstra(g, start): -    n = len(g) -    dist = [float("inf")] * (n)  # startからの最短距離 -    pending = n - 1  # 未確定の点の個数 -    dist[start] = 0 -    q = [(0, start)]  # (そこまでの距離、点) -    while q and pending: -        c, v = heappop(q) -        if dist[v] < c: -            continue -        pending -= 1 -        for to, cost in g[v]: -            if dist[v] + cost < dist[to]: -                dist[to] = dist[v] + cost -                heappush(q, (dist[to], to)) -    return dist - - -dist = dijkstra(g, 1) -print((dist[0] + 1)) +    g[i].append((10 * i % k, 0)) +res = bfs01(g, 1) +print((res[0] + 1))