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;
#define int long long
typedef unsigned long long ull;
typedef vector<ull> vec;
typedef vector<vec> mat;
typedef pair<int,ull> P;
#define N 4
ull po[N*N+10];
ull m2i(mat m){
  int res=0;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      res+=m[i][j]*po[i*N+j];
  return res;
}
mat i2m(ull x){
  mat res(N,vec(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      if(i==N-1&&j==N-1) res[i][j]=x/po[i*N+j];
      else res[i][j]=(x%po[i*N+j+1])/po[i*N+j];
  return res;
}
int dist(mat m){
  int res=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(!m[i][j]) continue;
      int k=m[i][j]-1;
      int y=k/N,x=k%N;
      res+=abs(i-y)+abs(j-x);
    }
  }
  return res;
}
signed main(){
  po[0]=1;
  for(int i=0;i<N*N;i++) po[i+1]=po[i]*(N*N);
  mat p(N,vec(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin>>p[i][j];
  mat e(p);
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      e[i][j]=i*N+j+1;
  e[N-1][N-1]=0;
  ull ans=m2i(e);
  priority_queue<P,vector<P>,greater<P> > q;
  map<ull,int> m;
  q.push(P(dist(p),m2i(p)));
  m[m2i(p)]=0;
  int ax[]={1,0,-1,0};
  int ay[]={0,1,0,-1};
  while(!q.empty()){
    P y=q.top();q.pop();
    ull x=y.second;
    if(x==ans) break;
    p=i2m(x);
    int zy,zx;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(p[i][j]==0)zy=i,zx=j;
    for(int k=0;k<4;k++){
      int ny=zy+ay[k],nx=zx+ax[k];
      if(ny<0||N<=ny||nx<0||N<=nx) continue;
      swap(p[zy][zx],p[ny][nx]);
      ull t=m2i(p);
      if(!m.count(t)||m[x]+1<m[t]){
        m[t]=m[x]+1;
        q.push(P(m[t]+dist(p),t));
      }
      swap(p[zy][zx],p[ny][nx]);
    }
  }
  cout<<m[ans]<<endl;
  return 0;
}