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:
//lec04
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string>
#include<cassert>

using namespace std;

#define n 4
#define n1 16
#define LIMIT 100


static const int x[4]={0,-1,0,1};
static const int y[4]={1,0,-1,0};
static const char c[4]={'r','u','l','d'};
int MDT[n1][n1];

struct Puzzle{
	int m[n1];
	int space;
	int MD;
};

Puzzle state;
int lim;
int path[LIMIT];

bool DFS(int depth, int s){
	if(state.MD==0){
		return true;

	}
	if(depth+state.MD>lim){
		return false;
	}
	int stx=state.space/n;
	int sty=state.space%n;
	Puzzle temp;

	for(int i=0;i<n;i++){
		int tx=stx+x[i];
		int ty=sty+y[i];
		if(tx<0||ty<0||tx>=n||ty>=n){
			continue;
		}
		int mmax=max(s,i);
		int mmin=min(s,i);
		if(mmax-mmin==2){
			continue;
		}
		temp=state;
		state.MD-=MDT[ty+tx*n][state.m[ty+tx*n]-1];
		state.MD+=MDT[sty+stx*n][state.m[ty+tx*n]-1];
		swap(state.m[ty+tx*n],state.m[sty+stx*n]);
		state.space=ty+tx*n;
		if(DFS(depth+1,i)){
			path[depth]=i;
			return true;
		}
		state=temp;

	}
	return false;
}


int get(Puzzle p){
	int sum=0;
	for(int i=0;i<n1;i++){
		if(p.m[i]==n1){
			continue;
		}
		int pp=p.m[i]-1;
		sum+=MDT[i][pp];
	}
	return sum;
}

string hanpu_depth(Puzzle in){
	in.MD=get(in);
	for(lim=in.MD;lim<=LIMIT;lim++){
		state=in;
		if(DFS(0,-100)){
			string a="";
			for(int i=0;i<lim;i++){
				a+=c[path[i]];
			}
			return a;
		}
	}
	return "unsolve";

}

int main(){
  for(int i=0;i<n1;i++){
  	for(int j=0;j<n1;j++){
  		MDT[i][j]=abs(i/n-j/n)+abs(i%n-j%n);
  	}
  }
  Puzzle input;
  for(int i=0;i<n1;i++){
  	cin>>input.m[i];
  	if(input.m[i]==0){
      input.m[i]=n1;
      input.space=i;
    }
  }
  string ans =hanpu_depth(input);
  cout<<ans.size()<<endl;
  return 0;
}