import java.util.*
import kotlin.*


fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = Scanner(System.`in`)
        val k = sc.nextInt()

        // kで割ってi余る数 桁和
        val min = Array(k) { Int.MAX_VALUE }
        val flag = Array(k) { false }
        val deq = ArrayDeque<Int>()
        min[1] = 1
        deq.add(1)

        while (deq.size > 0) {
            val p = deq.poll()
            if(flag[p]) continue
            flag[p] = true
            // 10倍 桁和は変わらない
            if (min[p] < min[(p * 10) % k]) {
                min[(p * 10) % k] = min[p]
                deq.push((p * 10) % k)
            }

            // +1 桁和 1増える
            // 一番下が9のときは探索済み
            if (min[p] + 1 < min[(p + 1) % k]) {
                min[(p + 1) % k] = min[p] + 1
                deq.add((p + 1) % k)
            }
        }
        println(min[0])
    }
}
