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

using namespace std;

#define N 4
#define N2 16
#define L 100

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

struct Puzzle{
  int f[N2];
  int space;
  int MD;
};

Puzzle state;
int limit,path[L];
int MDT[N2][N2];


bool isSolved();
bool dfs(int depth,int prev);
int Get(Puzzle pz);
string ID(Puzzle in);

int main(void){
  int i,j;
  string ans;
  Puzzle in;
  
  for(i = 0;i < N2;i++){
    for(j = 0;j < N2;j++){
      MDT[i][j] = abs(i/N-j/N) + abs(i%N-j%N);
    }
  }
    
  for(i = 0;i < N2;i++){
    cin >> in.f[i];
      
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }
    
  ans = ID(in);
  cout << ans.size() << endl;
    
  return 0;
}






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



bool dfs(int depth,int prev){
  int r;
  Puzzle temp;
  
  if(state.MD == 0){
    return true;
  }
    
  if(depth+state.MD > limit){
    return false;
  }
    
  int sx = state.space/N;
  int sy = state.space%N;
    
  for(r = 0;r < 4;r++){
    int tx = sx+dx[r];
    int ty = sy+dy[r];
	
    if(tx < 0 || ty < 0 || tx >= N || ty >= N){
      continue;
    }
	
    if(max(prev,r) - min(prev,r) == 2){
      continue;
    }
	
    temp = state;
	
    state.MD -= MDT[tx*N+ty][state.f[tx*N+ty]-1];
    state.MD += MDT[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,r)){
      path[depth] = r;
      return true;
    }
	
    state = temp;
  }
    
  return false;
}



int Get(Puzzle pz){
  int i;
  int sum = 0;
  
  for(i = 0;i < N2;i++){
    if(pz.f[i] == N2){
      continue;
    }
	
    sum += MDT[i][pz.f[i]-1];
  }
    
  return sum;
}



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