import scala.collection.mutable

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val k = sc.nextInt()
  var e = List[(Int, Int, Int)]()
  for (i <- 0 until k) {
    if (i % 10 != 9) {
      e ::= (i, (i+1) % k, 1)
    }
    e ::= (i, (10 * i) % k, 0)
  }

  val sp = binaryBfs(1, k, e)
  println(sp(0) + 1)

  def binaryBfs(s: Int, n: Int, edges: Seq[(Int, Int, Int)]): Array[Int] = {
    val adj = Array.fill(n)(List[(Int, Int)]())
    for ((u, v, w) <- edges) {
      adj(u) ::= (v, w)
    }

    val sp = Array.fill(n)(-1)
    sp(s) = 0
    val deque = mutable.ArrayDeque[Int]()
    deque.append(s)
    while (deque.nonEmpty) {
      val u = deque.removeHead()
      for ((v, w) <- adj(u) if (sp(v) == -1 || sp(u) + w < sp(v))) {
        sp(v) = sp(u) + w
        if (w == 0) {
          deque.prepend(v)
        } else {
          deque.append(v)
        }
      }
    }
    sp
  }
}
