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>
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

string s="";
string ans="123456789ABCDEF0";
int Limit=45,limit=0;
int d[4] = {-1,1,-4,4};
int dis[16][16]={};

string to(int a){
  if(a==10)return "A";
  if(a==11)return "B";
  if(a==12)return "C";
  if(a==13)return "D";
  if(a==14)return "E";
  if(a==15)return "F";
  stringstream ss;
  ss<<a;
  return ss.str();
}

int f(char c){
  if(c=='0')return 16;
  if('A'<=c && c<='F')return 10+(c-'A');
  return c-'0';
}

bool rec(string v,int c_index,int p_index,int step,int h){
  if(limit<step+h)return false;
  if(v==ans)return true;
  FOR(i,0,4){
    if(c_index%4==0 && d[i]==-1)continue;
    if((c_index+1)%4==0 && d[i]==1)continue;
    if(c_index<=3 && d[i]==-4)continue;
    if(12<=c_index && d[i]==4)continue;
    int n_index = c_index+d[i];
    if(n_index==p_index)continue;
    string u = v;
    int n_h=h-dis[n_index][f(v[n_index])-1]+dis[c_index][f(v[n_index])-1];
    swap(u[c_index],u[n_index]);
    if(rec(u,n_index,c_index,step+1,n_h))return true;
  }
  return false;
}

int solve(){
  int ind = 0,h = 0;
  FOR(i,0,16)FOR(j,0,16)dis[i][j]=abs(i/4-j/4)+abs(i%4-j%4);
  FOR(i,0,16){
    if(f(s[i])==16)continue;
    h+=dis[i][f(s[i])-1];
  }
  FOR(i,0,16)if(s[i]=='0')ind=i;
  FOR(i,h,Limit+1){
    limit=i;
    if(rec(s,ind,-1,0,h))return i;
  }
  return inf;
}

int main()
{
  FOR(i,0,16){
    int a;
    cin>>a;
    s+=to(a);
  }
  cout<<solve()<<endl;
  return 0;
}