
module M = Set.Make(struct
  type t = int * int
  let compare = compare
end)

let () =
  Scanf.scanf "%d" @@ fun k ->
  let (+%) a b = (a + b) mod k in
  let ( *%) a b = (a * b) mod k in

  let a = Array.make k k in
  a.(1) <- 1;
  let rec loop pq =
    if M.is_empty pq then () else begin
      let (d, m) = M.min_elt pq in
      let pq' = M.remove (d, m) pq in
      if d > a.(m) then loop pq' else
      [(d+1, m+%1); (d, m *% 10)] |> List.fold_left (fun q (d',m') ->
        if d' < a.(m') then begin
          a.(m') <- d';
          M.add (d', m') q
        end else q
      ) pq' |> loop
    end
  in
  loop (M.singleton (1, 1));
  Printf.printf "%d\n" a.(0)