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


short ans[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};

int diff1(short s1[4][4], short s2[4][4]){
  int sum=0;
  for(int i=0; i<4; i++){
    for(int j=0; j<4; j++){
      if(s1[i][j] != s2[i][j])sum++;
    }
  }
  return sum;
}


int diff2(short s1[4][4]){
  int sum = 0;
  for(int i=0; i<4; i++){
    for(int j=0; j<4; j++){
      int x,y; //correct pos
      if(s1[i][j]==0){ continue; }
      else{
	y = (s1[i][j]-1)/4;
	x = (s1[i][j]-1)%4;
      }
      
      sum += abs(i-y) + abs(j-x);
    }
  }
  return sum;
}


void swap(short& a, short& b){ int tmp=a; a=b; b=tmp; }


int solve(short state[4][4], int step, int depth, int sx,int sy, int prex, int prey){
  
  if(diff1(state,ans)==0)return step;
  if(step + diff2(state) > depth)return -1;

  //up
  if(sy>0 && sy-1 != prey){
    swap(state[sy][sx] , state[sy-1][sx]);
    int res=solve(state, step+1, depth, sx, sy-1, sx,sy);
    if(res != -1)return res;
    swap(state[sy][sx] , state[sy-1][sx]);
  }
  //down
  if(sy<3 && sy+1 != prey){
    swap(state[sy][sx] , state[sy+1][sx]);
    int res=solve(state, step+1, depth, sx, sy+1, sx,sy);
    if(res != -1)return res;
    swap(state[sy][sx] , state[sy+1][sx]);
  }
  //left
  if(sx>0 && sx-1 != prex){
    swap(state[sy][sx] , state[sy][sx-1]);
    int res=solve(state, step+1, depth, sx-1, sy, sx,sy);
    if(res != -1)return res;
    swap(state[sy][sx] , state[sy][sx-1]);
  }
  //right
  if(sx<3 && sx+1 != prex){
    swap(state[sy][sx] , state[sy][sx+1]);
    int res=solve(state, step+1, depth, sx+1, sy, sx,sy);
    if(res != -1)return res;
    swap(state[sy][sx] , state[sy][sx+1]);
  }

  return -1;
}



int main(){
  short input[4][4];
  int sx,sy;
  
  for(int i=0; i<4; i++){
    for(int j=0; j<4; j++){
      cin >> input[i][j];
      if(input[i][j]==0){ sx=j, sy=i; }
    }
  }


  
  int depth = 1;
  int step;
  while((step=solve(input,0,depth,sx,sy,sx,sy)) == -1 ){
    depth++;
  }

  cout << step << endl;

}