Scanf.scanf "%d" (fun k ->
    let arr = Array.make k (-1) in

    let deq = Array.make (2 * k) 0 in

    let rec loop f l =
        if f <= l then (
            let num = deq.(f) in
            let f = f + 1 in
            let cost = arr.(num) in
            let next = (num * 10) mod k in
            if arr.(next) < 0 || arr.(next) > cost then (
                arr.(next) <- cost;
                let f = f - 1 in
                deq.(f) <- next;
                loop f l
            );
            let next = (num + 1) mod k in
            if arr.(next) < 0 || arr.(next) > cost + 1 then (
                arr.(next) <- cost + 1;
                let l = l + 1 in
                deq.(l) <- next;
                loop f l
            );
        )
    in
    arr.(1) <- 1;
    deq.(k) <- 1;
    loop k k;
    Printf.printf "%d\n" arr.(0)
)