def dijkstra(dist, s, val, t):
    from heapq import heappop, heappush
    dist[s] = val
    queue = [(val, s)]
    while queue:
        val, node = heappop(queue)
        if dist[node] == val:
            for u, w in t(node, val):
                if dist[u] > w:
                    dist[u] = w
                    heappush(queue, (w, u))
    return dist
def solve(n):
    def t(re, add1):
        return [((re*10)%n, add1), ((re+1)%n, add1+1)]
    return dijkstra([n+1]*n, 1%n, 1, t)[0]
n=int(input())
print(solve(n))