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<cstdio>
#include<cstdlib>
#define N 4
using namespace std;

int mas[N][N];
int cpy[N][N];

void input() {

  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      cin>>mas[i][j];
}
void output() {

  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++) {
      printf("%3d", mas[i][j]);
      cout<<endl;
    }
}
void copy(int m[N][N], int t[N][N]) {

  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++) m[i][j] = t[i][j];
}
int calc() {
  int sum = 0;
  for(int i = 0; i < N*N; i++) {
    int v = mas[i/N][i%N];
    if(v) {
      v--;
      sum += abs(i/N-v/N)+abs(i%N-v%N);
    }
  }
  return sum;
}

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int is_in(int x, int y) {
  return 0<=x && x<N && 0<=y && y<N;
}
int dfs(int x, int y, int p, int dep, const int lim) {
  int h = calc();

  if(h == 0) return dep;
  if(dep+h > lim) return -1;

  for(int i = 0; i < N; i++) {
    int nx = x+dx[i], ny = y+dy[i], res;
    if(~p && i == (p+2)%N) continue;
    if(!is_in(nx, ny)) continue;
    swap(&mas[y][x], &mas[ny][nx]);
    res = dfs(nx, ny, i, dep+1, lim);
    if(~res) return res;
    swap(&mas[y][x], &mas[ny][nx]);
  }
  return -1;
}
void get_empty(int *x, int *y) {

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(!mas[i][j]) {
    *x = j;
    *y = i;
    return;
      }
    }
  }
}
int solve() {
  int x, y, lim, ans;
  get_empty(&x, &y);
  for(lim = 0; lim < 50; lim++) {
    copy(cpy, mas);
    if((ans = dfs(x, y, -1, 0, lim)) != -1) return ans;
    copy(mas, cpy);
  }
  return -1;
}
int main() {
  input();
  cout<<solve()<<endl;
  return 0;
}