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 <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define n1 4
#define n2 16
#define LIMIT 46
struct puzzle{
  int row[n2];
  int x,y;
  int MD;
};
int MDS[n2][n2];
 int dx[4]={0,-1,0,1};
 int dy[4]={1,0,-1,0};
int limit,path[LIMIT];
puzzle pstate;
int getallmd(puzzle p){
  int sum=0;
  for(int i=0;i<n2;i++)
    if(p.row[i]!=n2)sum+=MDS[i][p.row[i]-1];
  return sum;
}

bool dfs(int depth, int prev){
  if(pstate.MD==0)return true;
  if(depth+pstate.MD>limit)return false;
  int sx=pstate.x,sy=pstate.y;
  puzzle tmp;
  for(int i=0;i<4;i++){
    int tx=sx+dx[i];
    int ty=sy+dy[i];
    if(tx<0||ty<0||tx>=n1||ty>=n1)continue;
    if((int)(max(prev,i)-min(prev,i))==2)continue;
    tmp=pstate;
    pstate.MD-=MDS[tx*n1+ty][pstate.row[tx*n1+ty]-1];
    pstate.MD+=MDS[sx*n1+sy][pstate.row[tx*n1+ty]-1];
    swap(pstate.row[tx*n1+ty],pstate.row[sx*n1+sy]);
    pstate.x=tx;
    pstate.y=ty;
    //cout<<"finish; " <<i<<endl;
    if(dfs(depth+1,i))return true;
    pstate=tmp;
  }
  return false;
}
void findans(puzzle fp){
  fp.MD=getallmd(fp);
  for(limit=fp.MD;limit<=LIMIT;limit++){
    pstate=fp;
    if(dfs(0,-100))return;
  }
}

int main(){
  puzzle p;
  for(int i=0;i<n2;i++){
    cin>>p.row[i];
    if(p.row[i]==0){
      p.row[i]=n2;
      p.x=i/n1;
      p.y=i%n1;
    }
    for(int j=0;j<n2;j++)
      MDS[i][j]=abs(i/n1-j/n1)+abs(i%n1-j%n1);
  }
  findans(p);
  cout<<limit<<endl;


  return 0;
}