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:
#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

#define SIDE 4
#define N 16
#define LIMIT 100

struct Board {
  int state[N];
  int zero_pos;
  int md;
};

int DX[4] = { 0, 1, 0, -1 };
int DY[4] = { 1, 0, -1, 0 };
char DIR[4] = { 'u', 'r', 'd', 'l' };

int MDs[N][N];
int path[LIMIT];
Board b;
int limit;

bool dfs(int depth, int prev) {
  if (b.md == 0) return true;
  if (depth + b.md > limit) return false;

  int sx = b.zero_pos / SIDE;
  int sy = b.zero_pos % SIDE;

  Board tmp;

  for (int i = 0; i < 4; i++) {
    int new_x = sx + DX[i];
    int new_y = sy + DY[i];

    if (new_x < 0 || new_x >= SIDE || new_y < 0 || new_y >= SIDE) continue;
    if (max(prev, i) - min(prev, i) == 2) continue;

    tmp = b; // preserve current board

    b.md -= MDs[new_x * SIDE + new_y][b.state[new_x * SIDE + new_y] - 1];
    b.md += MDs[sx * SIDE + sy][b.state[new_x * SIDE + new_y] - 1];

    swap(b.state[sx * SIDE + sy], b.state[new_x * SIDE + new_y]);
    b.zero_pos = new_x * SIDE + new_y;

    if (dfs(depth + 1, i)) {
      path[depth] = i;
      return true;
    }

    b = tmp; // restore current board
  }

  return false;
}

int get_MD_sum(Board in) {
  int sum = 0;
  for (int i = 0; i < N; i++) {
    if (in.state[i] == N) continue;
    sum += MDs[i][in.state[i] - 1];
  }
  return sum;
}

void ida(Board in) {
  in.md = get_MD_sum(in);

  for (limit = in.md; limit <= LIMIT; limit++) {
    b = in;
    if (dfs(0, -100)) {
      string ans = "";
      for (int i = 0; i < limit; i++) ans += DIR[path[i]];

      cout << ans.size() << endl;
      return;
    }
  }
}

int main() {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      MDs[i][j] = abs(i / SIDE - j / SIDE) + abs(i % SIDE - j % SIDE);

  Board in; 

  for (int i = 0; i < N; i++) {
    cin >> in.state[i];
    if (in.state[i] == 0) {
      in.state[i] = N;
      in.zero_pos = i;
    }
  }

  ida(in);
}