open Printf
open Scanf

module Pqueue = struct

  type 'a t = {mutable cnt : int; hp : 'a array; cmp : 'a -> 'a -> int}

  let create n v f = {cnt = 0; hp = Array.make n v; cmp = f}

  let push k pq =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let p = i / 2 in
      if p = 0 || pq.cmp pq.hp.(p) pq.hp.(i) >= 0 then ()
      else (swap p i; iter p)
    in
    pq.cnt <- pq.cnt + 1;
    pq.hp.(pq.cnt) <- k;
    iter (pq.cnt)

  let max_heapify pq n =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let l = 2 * i in
      let r = 2 * i + 1 in
      let mi =
        let ti = if l <= pq.cnt && pq.cmp pq.hp.(l) pq.hp.(i) > 0 then l else i in
        if r <= pq.cnt && pq.cmp pq.hp.(r) pq.hp.(ti) > 0 then r else ti in
      if mi <> i then
        begin
          swap mi i;
          iter mi
        end
    in
    iter n

  let pop pq =
    let ret = pq.hp.(1) in
    pq.hp.(1) <- pq.hp.(pq.cnt);
    pq.cnt <- pq.cnt - 1;
    max_heapify pq 1;
    ret

  let top pq = pq.hp.(1)

  let is_empty pq = pq.cnt = 0

  let length pq = pq.cnt

end

let id x = x

type state = {mv : int; h : int; sp : int; bd : int array}
               
let () =
  let n = 4 in
  let isp = ref 0 in
  let bd = Array.init (n * n) (fun i -> let v = scanf "%d " id in if v = 0 then isp := i; v) in
  let dist bd = Array.fold_left (fun (i, d) x ->
                                 if x = 0 then (i+1, d)
                                 else
                                   let r, c = (i / n, i mod n) in
                                   let y = x - 1 in
                                   let r', c' = (y / n, y mod n) in
                                   (i + 1, d + abs (r - r') + abs (c - c'))
                                ) (0, 0) bd |> snd in
  let pq = Pqueue.create 2000000 {mv = 0; h = 0; sp = 0; bd = [||]} (fun x y -> y.mv + y.h - x.mv - x.h) in
  let ht = Hashtbl.create 100 in
  let rec loop () =
    if Pqueue.is_empty pq then failwith "15 puzzle"
    else
      let st = Pqueue.pop pq in
      if st.h = 0 then st.mv
      else begin
          List.iter (fun (dx, dy) ->
                     let x, y = (st.sp / n, st.sp mod n) in
                     let nx, ny = (dx + x, dy + y) in
                     if 0 <= nx && nx < n && 0 <= ny && ny < n then
                       let nsp = n * nx + ny in
                       let nbd = Array.copy st.bd in
                       begin
                         nbd.(st.sp) <- st.bd.(nsp);
                         nbd.(nsp) <- 0;
                         if Hashtbl.mem ht nbd then ()
                         else
                           let nst = {mv = st.mv + 1; h = dist nbd; sp = nsp; bd = nbd} in
                           Pqueue.push nst pq;
                           Hashtbl.replace ht nbd true
                       end
                    ) [(1,0);(0,1);(-1,0);(0,-1)];
          loop ()
        end                  
  in
  Pqueue.push {mv = 0; h = dist bd; sp = !isp; bd = bd} pq;
  Hashtbl.add ht bd true;
  loop () |> printf "%d\n"