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<assert.h>

template<typename T>
void swap(T &a,T &b){
  T x=a;
  a=b;
  b=x;
}

int dif(int x,int y){return x-y>=0?x-y:y-x;}

const int N = 4;
int st[N*N];

int calc(int i,int j){ 
  if(st[i*N+j]<0) return 0;
  int res=0; 
  res+=dif(i,st[i*N+j]/N);
  res+=dif(j,st[i*N+j]%N);
  return res;
}

int dist=0,ans=45;

int check(int cur){
  if(dist==0&&ans>cur) ans=cur;
  int val=cur+dist;
  return val<ans;  
}

int dy[]={0,0,1,-1};
int dx[]={1,-1,0,0};
int in(int y,int x){return 0<=y&&y<N&&0<=x&&x<N;};

void dfs(int di,int y,int x,int p){
  for(int k=0;k<4;k++){
    if((p>=0)&&((p^1)==k)) continue;
    int ny=y+dy[k],nx=x+dx[k];
    if(!in(ny,nx)) continue;
    dist-=calc(ny,nx);
    swap(st[y*N+x],st[ny*N+nx]);
    dist+=calc(y,x);
    if(check(di+1)) dfs(di+1,ny,nx,k);    
    dist-=calc(y,x);
    swap(st[y*N+x],st[ny*N+nx]);
    dist+=calc(ny,nx);
  }
}

int main(){
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      std::cin>>st[i*N+j],st[i*N+j]--;
  
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      dist+=calc(i,j);
  
  int y=-1,x=-1;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      if(st[i*N+j]<0) y=i,x=j;

  check(0);
  dfs(0,y,x,-1);
  
  std::cout<<ans<<std::endl;
  return 0;
}