Problem: The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 15 as shown below.


1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* The given puzzle is solvable in at most 45 steps.

Input

The $4 \times 4$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Output

8

Solution (in CPP):

Solution:
// 
// 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); }

int B[4][4], x, y;
int manhattan_distance = 0;
int md(int i, int j) {
  int a = B[i][j] - 1;
  return abs(a%4 - j) + abs(a/4 - i);
}
int move(int d) {
  int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};
  int X = x + dx[d], Y = y + dy[d];
  if (X < 0 || X >= 4 || Y < 0 || Y >= 4) return false;
  manhattan_distance -= md(X,Y);
  swap(B[x][y], B[X][Y]);
  manhattan_distance += md(x,y);
  x = X; y = Y;
  return true;
}

const int INF = 9999999;
int rbfs() {
  typedef pair<int, bool> result;
  function<result(int,int,int,int)> rec = [&](int depth, int prev, int lower, int bound) {
    if (lower > bound) return result(lower, false);
    if (manhattan_distance == 0) return result(depth, true);
    int score = manhattan_distance + depth;

    int F[4] = {INF+1, INF+1, INF+1, INF+1};
    for (int d = 0; d < 4; ++d) {
      if (abs(prev - d) == 2) continue;
      if (move(d)) {
        F[d] = depth + manhattan_distance + 1;
        if (score < lower) F[d] = min(F[d], lower);
        move((d + 2) % 4);
      }
    }

    while (1) {
      int d = 0, th = INF;
      for (int j = 0; j < 4; ++j) 
        if      (F[j] < F[d]) { th = F[d]; d = j; }
        else if (F[j] < th) { th = F[j]; }
      if (F[d] > bound) return result(F[d], false);
      move(d);
      result z = rec(depth + 1, d, F[d], min(bound, th));
      if (z.snd) return z;
      F[d] = z.fst;
      move((d + 2) % 4);
    }
  };
  printf("%d\n", rec(0, 100, 0, INF).fst);
  return 0;
}

int main() {
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      scanf("%d", &B[i][j]);
      if (B[i][j] == 0) { x = i, y = j; }
      else { manhattan_distance += md(i, j); }
    }
  }
  rbfs();
}