
module Q = struct
  type 'a t = { que : 'a Queue.t; stk : 'a Stack.t }
  exception Empty
  let create () = { que = Queue.create ();  stk = Stack.create () }
  let push_front v deq = Stack.push v deq.stk 
  let push_back v deq = Queue.push v deq.que
  let pop_front deq =
    if not (Stack.is_empty deq.stk) then
      Stack.pop deq.stk
    else if Queue.is_empty deq.que then
      raise Empty
    else
      Queue.pop deq.que
  let is_empty deq = Stack.is_empty deq.stk && Queue.is_empty deq.que
end

let () =
  let k = Scanf.scanf "%d" (fun x -> x) in
  let ( +@ ) x y = (x + y) mod k in
  let ( *@ ) x y = (x * y) mod k in
  let md = Array.make k k in
  md.(1) <- 1;
  let deq = Q.create () in
  Q.push_back 1 deq;
  while not (Q.is_empty deq) do
    let v = Q.pop_front deq in
    let w1, w2 = v *@ 10, v +@ 1 in
    if md.(v) < md.(w1) then (
      md.(w1) <- md.(v); Q.push_front (w1) deq);
    if md.(v) + 1 < md.(w2) then (
      md.(w2) <- md.(v) + 1;  Q.push_back (w2) deq)
  done;
  Printf.printf "%d\n" md.(0)
