def A(dist, start, startValue, traverse):
    from heapq import heappop, heappush
    dist[start] = startValue
    queue = [(startValue, start)]
    while queue:
        value, node = heappop(queue)
        if dist[node] == value:
            for node2, value2 in traverse(node, value):
                if dist[node2] > value2:
                    dist[node2] = value2
                    heappush(queue, (value2, node2))
    return dist
def B(n):
    def traverse(remainder, add1):
        return [((remainder*10)%n, add1), ((remainder+1)%n, add1+1)]
    return A([n+1]*n, 1%n, 1, traverse)[0]
n=int(input())
print(B(n))