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<bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
typedef long long ll;

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

int t[4][4];

int calc(){
  int res=0;
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      int id=t[i][j]-1;
      if(id==-1)continue;
      int y=id/4, x=id%4;
      res+= abs(y-i) + abs(x-j);
    }
  }
  return res;
}

int R;

bool dfs(int py,int px,int depth,int prev){
  int h=calc();
  if(h==0)return true;
  if(depth+h>R)return false;
  for(int i=0;i<4;i++){
    if( (i+2)%4 == prev )continue;
    int ny=py+dy[i];
    int nx=px+dx[i];
    if(ny<0 || nx<0 || ny>=4 || nx>=4)continue;
    swap(t[ny][nx],t[py][px]);
    if( dfs(ny,nx,depth+1,i) )return true;
    swap(t[ny][nx],t[py][px]);
  }
  return false;
}

int main(){
  int sy=0,sx=0;
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      cin>>t[i][j];
      if(t[i][j]==0){
        sy=i;
        sx=j;
      }
    }
  }
  for(R=0;R<=44;R++){
    if( dfs(sy,sx,0,-1) ){
      cout<<R<<endl;
      return 0;
    }
  }
  cout<<45<<endl;
  return 0;
}