import java.util.*

fun main(arg: Array<String>) {
    val k = readLine()!!.toInt()
    val edge = LinkedList<Pair<Int, Int>>()
    val score = Array<Int?>(k) { null }
    edge.add(Pair(1, 1))
    while (edge.isNotEmpty()) {
        val pair = edge.poll()
        val next1 = (pair.second * 10) % k
        val next2 = (pair.second + 1) % k
        score[pair.second] = pair.first
        if (pair.second == 0) break
        if (score[next1] == null) edge.push(Pair(pair.first, next1))
        if (score[next2] == null) edge.add(Pair(pair.first + 1, next2))
    }
    println(score[0])
}
