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 <iostream>
using namespace std;

#define N 16

int ans[N];
int cur[N];
int anspos[N];
int movepos[4] = {-4, 1, 4, -1};

int checkAns() {
  for (int i = 0; i < N; i++) {
    if (ans[i] != cur[i]) return 0;
  }
  return 1;
}

int calcEst() {
  int total = 0, t;
  for (int i = 0; i < N; i++) {
    if (cur[i]==0)continue;
    t = (i % 4) - (anspos[cur[i]] %4);
    if (t >= 0)
      total += t;
    else
      total -= t;

    t = (i / 4) - (anspos[cur[i]] / 4);
    if (t >= 0)
      total += t;
    else
      total -= t;
  }
  return total;
}

int dfs(int x, int px, int lim) {
  int res = -1, minres = -1;

  if (checkAns()) return 0;
  if (lim == 0) return -1;
  if (calcEst() > lim) return -1;
  for (int i = 0; i < 4; i++) {
    if (x + movepos[i] == px) continue;
    if ((x % 4 == 0 && movepos[i] == -1) || (x % 4== 3 && movepos[i] == 1))
      continue;
    if (x + movepos[i] >= N || x + movepos[i] < 0) continue;
    swap(cur[x], cur[x + movepos[i]]);
    res = dfs(x + movepos[i], x, lim - 1);
    if (res != -1) {
      if (minres == -1) {
        minres = res + 1;
      } else {
        minres = min(minres, res + 1);
      }
      break;
    }
    swap(cur[x], cur[x + movepos[i]]);
  }
  return minres;
}

int main() {
  int x, lim = 0, res;

  for (int i = 0; i < N; i++) ans[i] = i + 1;
  ans[N - 1] = 0;
  for (int i = 0; i < N; i++) anspos[i] = i - 1;
  anspos[0] = N - 1;

  for (int i = 0; i < N; i++) {
    cin >> cur[i];
    if (cur[i] == 0) x = i;
  }

  while (true) {
    res = dfs(x, x, lim);
    if (res >= 0) break;
    lim++;
  }

  // cout << lim << endl;
  cout << res << endl;
  return 0;
}