def dijkstra(dist, start, startValue, traverse):  # Dijkstra's algorithm
    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 A077196(n):
    def traverse(remainder, add1):
        return [((remainder*10)%n, add1), ((remainder+1)%n, add1+1)]
    return dijkstra([n+1]*n, 1%n, 1, traverse)[0]

n = int(input())
print(A077196(n))

# 我有一计，oeis————WZRYWZWY