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>
#include <unordered_set>
using namespace std;

typedef pair<int, int> P;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)

const int N=4;

struct state{
  vector<int> board;
  int dist;
  int bi,bj;
  int miss_cnt;
  int mh_dist;
  int pre;
};

int h0(const state& s){
  return s.dist;
}
int h1(const state& s){
  return s.dist+s.miss_cnt;
}
int h2(const state& s){
  return s.dist+s.mh_dist;
}

int di[]={0,1,0,-1};
int dj[]={1,0,-1,0};

int ans[N][N]={
  {0,1,2,3},
  {4,5,6,7},
  {8,9,10,11},
  {12,13,14,-1},
};

P ans_ps[N*N];

bool ida_star(const state& crtstate,char x){
  if(h2(crtstate)>x)return false;

  if(crtstate.mh_dist==0)return true;

  rep(dir,4){
    if(dir==crtstate.pre)continue;
    int bi=crtstate.bi;
    int bj=crtstate.bj;
    int ni=bi+di[dir];
    int nj=bj+dj[dir];
    if(ni<0||ni>=N||nj<0||nj>=N)continue;
    state nxtstate=crtstate;

    int num=crtstate.board[ni*N+nj];
    int ai=ans_ps[num].fi;
    int aj=ans_ps[num].se;
    nxtstate.mh_dist-=abs(ai-ni)+abs(aj-nj);
    nxtstate.miss_cnt+=(abs(ai-ni)+abs(aj-nj)==0?1:0);
    nxtstate.mh_dist+=abs(ai-bi)+abs(aj-bj);
    nxtstate.miss_cnt-=(abs(ai-ni)+abs(aj-nj)==0?1:0);

    swap(nxtstate.board[bi*N+bj],nxtstate.board[ni*N+nj]);
    nxtstate.dist++;
    nxtstate.bi=ni; nxtstate.bj=nj;
    nxtstate.pre=(dir+2)%4;
    if(ida_star(nxtstate,x))return true;
  }
  return false;
}

int main(){

  clock_t start=clock();

  rep(i,N)rep(j,N){
    if(ans[i][j]==-1)continue;
    ans_ps[ans[i][j]].fi=i;
    ans_ps[ans[i][j]].se=j;
  }

  state inistate;
  inistate.board=vector<int>(N*N);
  inistate.dist=0;
  inistate.mh_dist=0;
  inistate.pre=-1;
  rep(i,N)rep(j,N){
    int input;
    cin>>input;
    input--;
    inistate.board[i*N+j]=input;
    if(input==-1){
      inistate.bi=i;
      inistate.bj=j;
    }else{
      int ai=ans_ps[input].fi;
      int aj=ans_ps[input].se;
      inistate.mh_dist+=abs(ai-i)+abs(aj-j);
    }
  }

  rep(x,45+1){
    if(ida_star(inistate,x)){
      cout<<x<<endl;
      break;
    }
  }

  clock_t end=clock();
  //cerr<<"duration = "<<(double)(end-start)/CLOCKS_PER_SEC<<" sec."<<endl;

  return 0;
}