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>
#include <cmath>
#include <map>
#include <string>
#include <queue>

using namespace std;

static const int LIMIT = 100;
static const int N = 4;
static const char dir[4] = {'r', 'l', 'u', 'd'};
static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};

int MD[N*N][N*N];

class Puzzle {
 public:
  int v[N*N];
  int space_pos;
  int MD;
};

Puzzle state;
int limit;
int path[LIMIT];

bool isTarget(Puzzle& p) {
  for (int i = 0; i < N*N; i++) {
    if (state.v[i] != ((i+1) % (N*N))) {
      return false;
    }
  }
  return true;
}

int getAllMD(Puzzle& p) {
  int sum = 0;
  for (int i = 0; i < N*N; i++) {
    if (!p.v[i]) continue;
    sum += MD[p.v[i]-1][i];
  }
  return sum;
}

int dfs(int depth, int prev) {
  if (state.MD == 0) {
    return true;
  }
  if (depth + state.MD > limit) return false;
  for (int i = 0; i < 4; i++) {
    int sx = state.space_pos % N;
    int sy = state.space_pos / N;
    int tx = sx + dx[i];
    int ty = sy + dy[i];
    Puzzle tmp;
    if (tx >= 0 && tx < N &&
        ty >= 0 && ty < N &&
        max(prev, i) - min(prev, i) != 2) {
      tmp = state;
      state.MD -= MD[tx+ty*N][state.v[tx+ty*N]-1];
      state.MD += MD[sx+sy*N][state.v[tx+ty*N]-1];
      swap(state.v[sx+sy*N], state.v[tx+ty*N]);
      state.space_pos = tx+ty*N;
      if (dfs(depth+1, i)) {
        path[depth] = i;
        return true;
      }
      state = tmp;
    }
  }
  return false;
}

string iterative_deepening(Puzzle& in) {
  in.MD = getAllMD(in);

  for (limit = in.MD; limit <= LIMIT; limit++) {
    state = in;
    if (dfs(0, -100)) {
      string ans = "";
      for (int i = 0; i < limit; i++) {
        ans += dir[path[i]];
      }
      return ans;
    }
  }
}

int main() {
  for (int i = 0; i < N*N; i++) {
    for (int j = 0; j < N*N; j++) {
      MD[i][j] = abs(i/N - j/N) + abs(i%N - j%N);
    }
  }
  Puzzle p;
  for (int i = 0; i < N*N; i++) {
    cin >> p.v[i];
    if (!p.v[i]) p.space_pos = i;
  }
  cout << iterative_deepening(p).size() << endl;
  return 0;
}