fun main(arg: Array<String>) {
    val K = nextInt()
    val ans = IntArray(K) { Int.MAX_VALUE }
    val visit = BooleanArray(K)
    val deque = java.util.LinkedList<Int>()
    ans[1] = 1
    deque.addLast(1)
    while (!deque.isEmpty()) {
//System.err.println(deque.asIterable().joinToString())
        val e = deque.pollFirst()!!
        if (visit[e]) continue
        visit[e] = true
        if (ans[e] < ans[(e * 10) % K]) {
            ans[(e * 10) % K] = ans[e]
            deque.addFirst((e * 10) % K)
        }
        if (ans[e] + 1 < ans[(e + 1) % K]) {
            ans[(e + 1) % K] = ans[e] + 1
            deque.addLast((e + 1) % K)
        }
    }
    println(ans[0])
}

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun listOfString() = next().split(" ")
fun listOfInt(d: Int = 0) = listOfString().map { Integer.parseInt(it) + d }
fun listOfLong() = listOfString().map(String::toLong)
