def a(n):
    queue = [(0, 0)]  # 用队列存储 (当前值, 加1操作次数) 的元组，初始为 (0, 0)
    visited = set()  # 用于记录已经访问过的数值，避免重复计算

    while queue:
        current_value, add_ones_count = queue.pop(0)

        if current_value % n == 0 and current_value > 0:
            return add_ones_count

        if current_value not in visited:
            visited.add(current_value)

            # 进行乘以10的操作
            queue.append((current_value * 10, add_ones_count))

            # 进行加1的操作
            queue.append((current_value + 1, add_ones_count + 1))
n=int(input())
result = a(n)
print(result)