#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <stack>
#include <tuple>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

const int dr[4] = {0, 1, 0, -1};
const int dc[4] = {1, 0, -1, 0};

template <typename T> class Board {
public:
  static const int L = 4;
  static const int N = L * L;

  Board() : prohibited_dir(-1) {}
  Board(T *board) : prohibited_dir(-1) {
    // std::memcpy(board, this->board, sizeof(T) * N);
    for (int i = 0; i < N; i++) {
      this->board[i] = board[i];
    }
  }
  Board(const Board &b) : prohibited_dir(b.prohibited_dir), cost(b.cost) {
    // std::memcpy(board, this->board, sizeof(T) * N);
    for (int i = 0; i < N; i++) {
      this->board[i] = b.board[i];
    }
  }

  const T &operator[](std::size_t i) const { return board[i]; }
  T &operator[](std::size_t i) { return board[i]; }

  const T &as_plane(std::size_t r, std::size_t c) const {
    return board[plane2line(r, c)];
  }

  bool operator==(const Board &b) const {
    if (prohibited_dir != b.prohibited_dir)
      return false;
    for (int i = 0; i < N; i++) {
      if (board[i] != b.board[i])
        return false;
    }
    return true;
  }

  std::tuple<int, int> line2plane(int i) {
    return std::make_tuple(i / L, i % L);
  }

  int plane2line(int r, int c) { return r * L + c; }

  int L1(int sr, int sc, int dr, int dc) {
    int r = std::abs(sr - dr);
    int c = std::abs(sc - dc);
    return r + c;
  }

  bool is_goal() {
    for (int i = 0; i < N - 1; i++) {
      if (board[i] != i + 1)
        return false;
    }
    return board[N - 1] == 0;
  }

  int h() { return cost; }

  int calc_cost(int src) {
    if(board[src] == 0) return 0;
    int sr, sc;
    std::tie(sr, sc) = line2plane(src);
    int dr, dc;
    std::tie(dr, dc) = line2plane(board[src] - 1);
    return L1(sr, sc, dr, dc);
  }

  void h_init() {
    cost = 0;
    for (int src = 0; src < N; src++) {
      cost += calc_cost(src);
    }
#ifdef EBUG
    cout << "h_init() -> " << cost << endl;
    print();
#endif
  }

  bool is_in(int r, int c) { return 0 <= r && r < L && 0 <= c && c < L; }

  std::vector<Board<T>> neighbor() {
    std::vector<Board<T>> res;
    int zero;
    int zr, zc;
    for (int i = 0; i < N; i++) {
      if (board[i] == 0) {
        std::tie(zr, zc) = line2plane(i);
        zero = i;
      }
    }

    for (int i = 0; i < 4; i++) {
      if (prohibited_dir == i)
        continue;
      int nr = zr + dr[i], nc = zc + dc[i];
      int nxt = plane2line(nr, nc);
      if (!is_in(nr, nc))
        continue;
      Board next(*this);
      std::swap(next.board[zero], next.board[nxt]);
      next.prohibited_dir = (i + 2) % 4;
      next.cost -= calc_cost(nxt);
      // next.cost -= calc_cost(zero);
      // next.cost += next.calc_cost(nxt);
      next.cost += next.calc_cost(zero);
#ifdef EBUG
      next.print();
      cout << "=====cost of ↑ is " << next.cost << endl;
#endif
      res.push_back(next);
    }
    return res;
  }

#ifdef EBUG
  void print() {
    for (int r = 0; r < L; r++) {
      for (int c = 0; c < L; c++) {
        int idx = plane2line(r, c);
        cout << std::setw(3) << std::right << board[idx] << " ";
        ;
      }
      cout << endl;
    }
  }
#endif

protected:
  int prohibited_dir;
  int cost;

private:
  T board[N];
};

const int FOUND = (1 << 30) + 1;
const int INF = (1 << 30);

std::vector<Board<int>> ida_star(Board<int> root);
int search(std::vector<Board<int>> &path, int g, int bound);

#ifdef EBUG
int max_path_size = 0;
#endif

int main(void) {
  Board<int> board;
  int tmp[Board<int>::N];
  for (int i = 0; i < Board<int>::N; i++) {
    cin >> tmp[i];
  }
  board = Board<int>(tmp);
  board.h_init();

  std::vector<Board<int>> path = ida_star(board);
  cout << path.size() - 1 << endl;

#ifdef EBUG
  for (auto &p : path) {
    p.print();
  }
  cout << max_path_size << endl;
#endif
}

std::vector<Board<int>> ida_star(Board<int> root) {
  int bound = root.h();
  std::vector<Board<int>> path;
  path.reserve(50);
  path.push_back(root);
  while (1) {
    int t = search(path, 0, bound);
    if (t == FOUND)
      return path;
    if (t == INF)
      assert(false);
    bound = t;
  }
}

int search(std::vector<Board<int>> &path, int g, int bound) {
#ifdef EBUG
  max_path_size = std::max(max_path_size, (int)path.size());
#endif
  Board<int> node = path.back();
  int f = g + node.h();
  if (f > bound)
    return f;
  if (node.is_goal())
    return FOUND;
  int minv = INF;
  for (const auto &succ : node.neighbor()) {
    if (std::find(path.begin(), path.end(), succ) == path.end()) {
      path.push_back(succ);
      int t = search(path, g + 1, bound);
      if (t == FOUND)
        return FOUND;
      if (t < minv)
        minv = t;
      path.pop_back();
    }
  }
  return minv;
}



Measured memory_bytes: 3116