let rec take_while pred = function
    [] -> []
  | x::xs -> if pred x then x :: take_while pred xs else []

let rec scan_n n f v = if n <= 0 then [] else v :: scan_n (n-1) f (f v)

let arr = Array.init 101010 (fun i -> i)
let () = Scanf.scanf "%d" (fun n ->
  scan_n n succ 1 |> List.iter (fun i ->
    [6; 9] |> List.iter (fun m ->
      scan_n 10 (( * ) m) 1 |> take_while ((>=) i) |> List.iter (fun j ->
        arr.(i) <- min arr.(i) (arr.(i - j) + 1))));
  Printf.printf "%d\n" arr.(n))
