fun main(arg: Array<String>) {
    val k = readLine()!!.toInt()
    if (k == 1) {
        println(1)
        return
    }
    val po: Array<Int?> = Array(k) { null }
    po[1] = 1
    var searchSet = setOf(1)
    while (searchSet.isNotEmpty()) {
        val newSet: MutableSet<Int> = mutableSetOf()
        searchSet.forEach {
            val next1 = (it * 10) % k
            val next2 = (it + 1) % k
            if (po[next1] == null || po[it]!! < po[next1]!!) {
                po[next1] = po[it]
                newSet.add(next1)
            }
            if (po[next2] == null || po[it]!! + 1 < po[next2]!!) {
                po[next2] = po[it]!! + 1
                newSet.add(next2)
            }
        }
        searchSet = newSet
    }
    println(po[0])
}
