class FifteenPuzzle
  N = 4
  N2 = N * N
  LIMIT = 100
  DX = [ 0, 1, 0, -1 ]
  DY = [ 1, 0, -1, 0 ]
  DIR = [ 'u', 'r', 'd', 'l' ]
  MDTable = Array.new(N2).map { Array.new(N2) }

  class Puzzle
    attr_accessor :space, :f, :md

    def initialize
      @f = []
    end

    # get current md
    def get_all_md
      sum = 0
      (0...N2).each do |i|
        sum += MDTable[i][@f[i] - 1] if @f[i] != N2
      end
      return sum
    end

    def initialize_copy(obj)
      @f = obj.f.dup
      @space = obj.space
      @md = obj.md
    end

  end

  def initialize
    # init MDtable
    (0...N2).each do |i|
      (0...N2).each do |j|
        MDTable[i][j] = get_manhattan_distance(i % N, i / N, j % N, j / N)
      end
    end

    @puzzle = Puzzle.new
    4.times do |i|
      gets.split.map(&:to_i).each_with_index do |c, j|
        k = (4 * i) + j
        if c == 0
          @puzzle.f[k] = N2
          @puzzle.space = k
        else
          @puzzle.f[k] = c
        end
      end
    end

    @limit = 0
    @path = Array.new(LIMIT)
    @state = nil
  end

  def dfs(depth, prev)
    return true if @state.md == 0
    return false if depth + @state.md > @limit
    sx = @state.space / N
    sy = @state.space % N
    tmp = nil

    (0...4).each do |r|
      tx = sx + DX[r]
      ty = sy + DY[r]
      next if tx < 0 || N <= tx || ty < 0 || N <= ty
      next if [ prev, r ].max - [ prev, r ].min == 2
      tmp = @state.clone
      @state.md -= MDTable[tx * N + ty][@state.f[tx * N + ty] - 1]
      @state.md += MDTable[sx * N + sy][@state.f[tx * N + ty] - 1]
      @state.f[tx * N + ty], @state.f[sx * N + sy] = @state.f[sx * N + sy], @state.f[tx * N + ty]
      @state.space = tx * N + ty
      if dfs(depth + 1, r)
        @path[depth] = r
        return true
      end
      @state = tmp
    end
    return false
  end

  def iterative_deepening
    @puzzle.md = @puzzle.get_all_md

    (@puzzle.md..LIMIT).each do |limit|
      @state = @puzzle.clone
      @limit = limit
      if q = dfs(0, -100)
        ans = ""
        (0...limit).each { |i| ans += DIR[@path[i]] if @path[i] }
        return ans
      end
    end
    return -1
  end

  def get_manhattan_distance(x1, y1, x2, y2)
    return (x1 - x2).abs + (y1 - y2).abs
  end

end

fp = FifteenPuzzle.new
ans = fp.iterative_deepening
puts ans.length