let area =
  [| [1; 4]
   ; [0; 2; 5]
   ; [1; 3; 6]
   ; [2; 7]
   ; [0; 5; 8]
   ; [1; 4; 6; 9]
   ; [2; 5; 7; 10]
   ; [3; 6; 11]
   ; [4; 9; 12]
   ; [5; 8; 10; 13]
   ; [6; 9; 11; 14]
   ; [7; 10; 15]
   ; [8; 13]
   ; [9; 12; 14]
   ; [10; 13; 15]
   ; [11; 14] |]

let m_d =
  [| [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
   ; [|0; 1; 2; 3; 1; 2; 3; 4; 2; 3; 4; 5; 3; 4; 5; 6|]
   ; [|1; 0; 1; 2; 2; 1; 2; 3; 3; 2; 3; 4; 4; 3; 4; 5|]
   ; [|2; 1; 0; 1; 3; 2; 1; 2; 4; 3; 2; 3; 5; 4; 3; 4|]
   ; [|3; 2; 1; 0; 4; 3; 2; 1; 5; 4; 3; 2; 6; 5; 4; 3|]
   ; [|1; 2; 3; 4; 0; 1; 2; 3; 1; 2; 3; 4; 2; 3; 4; 5|]
   ; [|2; 1; 2; 3; 1; 0; 1; 2; 2; 1; 2; 3; 3; 2; 3; 4|]
   ; [|3; 2; 1; 2; 2; 1; 0; 1; 3; 2; 1; 2; 4; 3; 2; 3|]
   ; [|4; 3; 2; 1; 3; 2; 1; 0; 4; 3; 2; 1; 5; 4; 3; 2|]
   ; [|2; 3; 4; 5; 1; 2; 3; 4; 0; 1; 2; 3; 1; 2; 3; 4|]
   ; [|3; 2; 3; 4; 2; 1; 2; 3; 1; 0; 1; 2; 2; 1; 2; 3|]
   ; [|4; 3; 2; 3; 3; 2; 1; 2; 2; 1; 0; 1; 3; 2; 1; 2|]
   ; [|5; 4; 3; 2; 4; 3; 2; 1; 3; 2; 1; 0; 4; 3; 2; 1|]
   ; [|3; 4; 5; 6; 2; 3; 4; 5; 1; 2; 3; 4; 0; 1; 2; 3|]
   ; [|4; 3; 4; 5; 3; 2; 3; 4; 2; 1; 2; 3; 1; 0; 1; 2|]
   ; [|5; 4; 3; 4; 4; 3; 2; 3; 3; 2; 1; 2; 2; 1; 0; 1|] |]

let h a =
  let rec doit i acc =
    if i = 16 then acc
    else doit (i + 1) (acc + m_d.(a.(i)).(i))
  in doit 0 0

let idx_by_val x (a : int array) =
  let n = Array.length a in
  let rec doit i =
    if i = n then raise Not_found
    else if x = a.(i) then i
    else doit (i + 1)
  in doit 0

let solve a =
  let goal = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 0|] in
  let rec idastar i limit space_i moved lower =
    if i = limit then begin
      if a = goal then (Printf.printf "%d\n" (List.length moved - 1); exit 0)
    end else
      let rec move = function
        | [] -> ()
        | j :: js ->
          let x = a.(j) in
          if x <> List.hd moved then begin
            let new_lower = lower - m_d.(x).(j) + m_d.(x).(space_i) in
            if new_lower + i <= limit then begin
              a.(j) <- 0;
              a.(space_i) <- x;
              idastar (i + 1) limit j (x :: moved) new_lower;
              a.(j) <- x;
              a.(space_i) <- 0;
            end
          end;
          move js
      in move area.(space_i)
  in
  let lower = h a in
  let rec doit limit =
    if limit <= 45 then begin
      idastar 0 limit (idx_by_val 0 a) [-1] lower;
      doit (limit + 1)
    end in
  doit lower

let () =
  solve (Array.init 16 (fun _ -> Scanf.scanf "%d " (fun i -> i)))