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<algorithm>
#include<cmath>
#define N 4
#define N2 16
#define MAX 100
using namespace std;

int dx[N] = {0, -1, 0, 1};
int dy[N] = {1, 0, -1, 0};
char dc[N] = {'r', 'u', 'l', 'd'};
int puz[N2][N2];

struct puzzle{
  int f[N2];
  int space;
  int x;
};

puzzle state;
int lim;
int path[MAX];

int getAll(puzzle pzl){
  int sum = 0;

  for(int i = 0; i < N2; i++){
    if(pzl.f[i] == N2) continue;
    sum += puz[i][pzl.f[i]-1];
  }

  return sum;
  
}

bool Solv(){
  for(int i = 0; i < N2; i++){
    if(state.f[i] != (i+1)) return false;
  }
  
  return true;
  
}

bool dfs(int depth, int prev){
  if(state.x == 0) return true;
  if((depth + state.x) > lim) return false;

  int sx = state.space / N;
  int sy = state.space % N;

  puzzle dummy;

  for(int i = 0; i < N; i++){
    int tx = sx + dx[i];
    int ty = sy + dy[i];

    if(tx < 0 || ty < 0 || tx >= N || ty >=N) continue;
    if(max(prev, i) - min(prev, i) == 2) continue;

    dummy = state;

    state.x -= puz[tx*N + ty][state.f[tx*N + ty] - 1];
    state.x += puz[sx*N + sy][state.f[tx*N + ty] - 1];

    swap(state.f[tx*N + ty], state.f[sx*N + sy]);

    state.space = tx * N + ty;

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

      return true;
      
    }

    state = dummy;
    
  }

  return false;
  
}

string iterative(puzzle in){
  in.x = getAll(in);

  for(lim = in.x; lim < MAX; lim++){
    state = in;

    if(dfs(0, -100)){
      string ans = "";

      for(int i = 0; i < lim; i++){
	ans += dc[path[i]];
      }

      return ans;
      
    }
  }

  return "unsolvable";
  
}

int main(){

  for(int i = 0; i < N2; i++){
    for(int j = 0; j < N2; j++){
      puz[i][j] = abs(i/N - j/N) + abs(i%N - j%N);
    }
  }

  puzzle in;

  for(int i = 0; i < N2; i++){
    cin >> in.f[i];

    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }

  string ans = iterative(in);

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

  return 0;
  
}