import java.util.*

data class State(val v: Int, val w: Int)

fun main(args: Array<String>) {
  val k = readLine()!!.toInt()
  val visited = BooleanArray(k)
  val queue = ArrayDeque<State>()
  queue.offerLast(State(1, 1))
  while (queue.isNotEmpty()) {
    val s = queue.pollFirst()
    if (visited[s.v]) continue
    visited[s.v] = true

    if (s.v == 0) {
      println(s.w)
      return
    }

    val s1 = State((s.v * 10) % k, s.w)
    if (!visited[s1.v]) {
      queue.offerFirst(s1)
    }
    val s2 = State((s.v * 10 + 1) % k, s.w + 1)
    if (!visited[s2.v]) {
      queue.offerLast(s2)
    }
  }
  throw RuntimeException()
}
