import java.util.*

fun main(arg: Array<String>) {
    val k = readLine()!!.toInt()
    val edge = LinkedList(listOf(1 to 1))
    val score = IntArray(k) { -1 }
    while (edge.isNotEmpty()) {
        val (f, s) = edge.poll()
        score[s] = f
        if (s == 0) break
        val next1 = (s * 10) % k
        val next2 = (s + 1) % k
        if (score[next1] < 0) edge.push(Pair(f, next1))
        if (score[next2] < 0) edge.add(Pair(f + 1, next2))
    }
    println(score[0])
}
