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;

int limit=0,T[4][4];

int evaluate(){
  int cx[]={3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2},cy[]={3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3};
  int ret=0;
  for (int i=0;i<4;i++){
    for (int j=0;j<4;j++){
      int ti = T[i][j];
      if (ti==0)continue;
      ret+=abs(cx[ti]-j);
      ret+=abs(cy[ti]-i);
      // if (cx[ti]!=j||cy[ti]!=i)ret++;
    }
  }
  return ret;
}

bool trymove(int c,int zx,int zy,int pzx,int pzy){
  int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
  if (evaluate()==0)return true;
  if (c+evaluate()>limit)return false;
  for (int i=0;i<4;i++){
    if (0>zx+dx[i]||zx+dx[i]>3||0>zy+dy[i]||zy+dy[i]>3)continue;
    if (zx+dx[i]==pzx&&zy+dy[i]==pzy)continue;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
    if (trymove(c+1,zx+dx[i],zy+dy[i],zx,zy)) return true;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
  }
  return false;
}

int main(){
  int zx,zy;
  for (int i=0;i<4;i++){
    for (int j=0;j<4;j++){
      cin >> T[i][j];
      if (T[i][j]==0){
	zx=j;
	zy=i;
      }
    }
  }
  
  while (evaluate()){
    limit++;
    if (trymove(0,zx,zy,zx,zy))break;
  }
  
  cout << limit << endl;
  
  return 0;
}