// 
// Fifteen Puzzle (Recursive Best First Search)
//
// ?????????????????????????????£???????°??????????????????????
//

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <unordered_set>

using namespace std;

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }

const int n = 4;
struct node {
  int B[n][n];
  int x, y; // zero position
  int depth; 
  int manhattan_distance;

  int md(int i, int j) {
    if (B[i][j] == 0) return 0;
    int x = B[i][j] - 1;
    return abs(x%4 - j) + abs(x/4 - i);
  }
  void init() {
    depth = 0;
    manhattan_distance = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (B[i][j] == 0) { x = i; y = j; }
        else manhattan_distance += md(i, j);
      }
    }
    //cout << "manhattan distance = " << manhattan_distance << endl;
  }
  bool move(int d) {  // [0 1 2 3] = [L D R U]
    int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};
    int X = x + dx[d], Y = y + dy[d];
    if (X < 0 || X >= n || Y < 0 || Y >= n) return false;
    manhattan_distance -= md(X,Y) + md(x,y);
    swap(B[x][y], B[X][Y]);
    manhattan_distance += md(x,y) + md(X,Y);
    x = X; y = Y;
    depth += 1;
    return true;
  }
  int score() const {
    return depth + manhattan_distance;
  }
  bool is_goal() const {
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        if (i == 3 && j == 3) continue;
        if (B[i][j] != 4*i+j+1) return false;
      }
    }
    return true;
  }
  bool operator<(const node &x) const {
    return score() > x.score();
  }
  long long hash() const {
    /* 
    long long h = 0, p = 1e9+7;
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j)
        h = (h * p) + B[i][j];
    return h;
    */

    vector<int> x(16);
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j)
        x[4*i+j] = B[i][j];
    int n = x.size();
    vector<int> y(n);
    for (int i = 0; i < n; ++i) y[x[i]] = i;
    long long c = 0, fac = 1;
    for (; n > 1; --n) {
      c += fac * x[n-1]; fac *= n;
      swap(x[n-1], x[y[n-1]]);
      swap(y[n-1], y[x[y[n-1]]]);
    }
    return c;
  }
};
void search_Astar(node root) {
  unordered_set<long long> seen;
  priority_queue<node> que;
  que.push(root);
  while (!que.empty()) {
    node u = que.top(); que.pop();
    long long h = u.hash();
    if (seen.count(h)) continue;
    seen.insert(h);
    //cout << u.score() << endl;
    if (u.is_goal()) { cout << u.score() << endl; return ; }
    for (int d = 0; d < 4; ++d) {
      node v = u;
      if (v.move(d)) que.push(v);
    }
  }
}
// recursive best first searh
void search(node root) {
  unordered_set<long long> seen;
  typedef pair<int, bool> result;
  function<result(const node&,int,int)> rec = 
    [&](const node &u, int lower, int bound) {

    long long h = u.hash();
    seen.insert(h);
    //cout << "u.score() = " << u.score() << endl;

    /*
    cout << "---" << endl;
    cout << "lower = " << lower << endl;
    cout << "bound = " << bound << endl;
    cout << "manhattan = " << u.manhattan_distance << endl;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        cout << u.B[i][j] << " ";
      }
      cout << endl;
    }
    */

    if (lower > bound) { seen.erase(h); return result(lower, false); }
    if (u.is_goal()) { seen.erase(h); return result(u.score(), true); }

    vector<pair<node,int>> next;
    for (int d = 0; d < 4; ++d) {
      node v = u; 
      if (v.move(d)) {
        long long hh = v.hash();
        if (seen.count(hh)) continue;
        if (u.score() < lower) next.push_back({v, min(lower, v.score())});
        else                   next.push_back({v, v.score()});
      }
    }
    if (next.size() == 0) { seen.erase(h); return result(9999999, false); }
    while (1) {
      int i = 0, threshold = 99999999;
      for (int j = 0; j < next.size(); ++j) {
        if (next[j].snd < next[i].snd) {
          threshold = next[i].snd; i = j;
        } else if (next[j].snd < threshold) {
          threshold = next[j].snd;
        }
      }
      if (next[i].snd > bound) {
        seen.erase(h);
        return result(next[i].snd, false);
      }
      result z = rec(next[i].fst, next[i].snd, min(bound, threshold));
      if (z.snd) { seen.erase(h); return z; }
      next[i].snd = z.fst;
    }
  };
  result z = rec(root, 0, 9999999);
  cout << z.fst << endl;
}


int main() {
  node root;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j)
      scanf("%d", &root.B[i][j]);
  root.init();
  search_Astar(root);
}

Measured memory_bytes: 196744