require 'pp'

width = 4
height = 4

# ???????????¢??¶?????????
end_panels = []
height.times do |i|
  end_panels << STDIN.gets.chomp.split(' ').map(&:to_i)
end
end_panels.flatten!
end_panels = end_panels.map{|n| n.to_s(16)}.join

start_panels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0].map{|n| n.to_s(16)}.join
$queue = ["t#{start_panels}", "f#{end_panels}"]
forward_cache = {}
backward_cache = {}

def add_queue(is_forward, panels, dicts, dict)
  q = if is_forward then "t" else "f" end
  q << panels
  q << dicts.dup
  q << dict
  $queue << q
end

while true do
  q = $queue.shift
  is_forward = if q[0] == "t" then true else false end
  panels = q.slice(1, 16)
  dicts = q.slice(17, q.size - 1) || ""
  # ?????°???1??¶????§????
  z = panels.index("0")
  if dicts.size > 0
    case dicts[-1]
    when "u" then panels[z], panels[z-height] = panels[z-height], panels[z]
    when "d" then panels[z], panels[z+height] = panels[z+height], panels[z]
    when "l" then panels[z], panels[z-1] = panels[z-1], panels[z]
    when "r" then panels[z], panels[z+1] = panels[z+1], panels[z]
    end
    z = panels.index("0")
  end
  # ?????£????????\????????§
  phex = panels.hex
  is_forward_cache = forward_cache.key?(phex)
  is_backward_cache = backward_cache.key?(phex)
  forward_cache_value = if is_forward_cache then forward_cache[phex] else 0 end
  backward_cache_value = if is_backward_cache then backward_cache[phex] else 0 end
  # ??????????????????
  if is_forward && is_backward_cache
    puts dicts.size + backward_cache_value
    break
  elsif !is_forward && is_forward_cache
    puts dicts.size + forward_cache_value
    break
  end
  # ?????£????????\??????????????¢??§?????°??????????????°??????????´¢?????¢??????
  if (is_forward && is_forward_cache && forward_cache_value <= dicts.size) || \
     (!is_forward && is_backward_cache && backward_cache_value <= dicts.size)
    next
  end
  # ??°???????????¢?????????????????????????????£????????\??????
  if is_forward
    if !is_forward_cache || forward_cache_value > dicts.size
      forward_cache[phex] = dicts.size
    end
  else
    if !is_backward_cache || backward_cache_value > dicts.size
      backward_cache[phex] = dicts.size
    end
  end
  # ?????§45???????????§????????\?????????????????¢?´¢?????????????????´???????????¢?´¢?????????
  if dicts.size >= 23
    next
  end
  # ?¬??????¢?´¢?????????
  if z / width != 0 \
     && !dicts.end_with?("d", "ddu", "ddduu")
    add_queue(is_forward, panels, dicts, "u")
  end
  if z / width != height - 1 \
     && !dicts.end_with?("u", "uud", "uuudd")
    add_queue(is_forward, panels, dicts, "d")
  end
  if z % width != 0 \
     && !dicts.end_with?("r", "rrl", "rrrll")
    add_queue(is_forward, panels, dicts, "l")
  end
  if z % width != width - 1 \
     && !dicts.end_with?("l", "llr", "lllrr")
    add_queue(is_forward, panels, dicts, "r")
  end
end