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:
//By Vlgd
#include<bits/stdc++.h>
#define ass printf("ÒŠ¤Ä¤±¤Þ¤·¤¿\n");
#define LIMIT 45
using namespace std;
const int N=4,NN=16;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int MDT[NN][NN],lim,ans=0; 
struct Puz{int pic[NN],space,path,MD;};
bool dfs(int dep,int prev,Puz cur){	
	if(cur.MD==0){
		ans=cur.path;
		return true;
	}
	if(dep+cur.MD>lim) return false;
	int sx=cur.space/N,sy=cur.space%N;
	for(int i=0;i<4;i++){
		Puz nxt=cur;
		int tx=sx+dx[i],ty=sy+dy[i];
		if(tx<0||ty<0||tx>=N||ty>=N) continue;
		if(max(i,prev)-min(i,prev)==2) continue;
		nxt.MD-=MDT[tx*N+ty][cur.pic[tx*N+ty]-1];
		nxt.MD+=MDT[sx*N+sy][cur.pic[tx*N+ty]-1];
		swap(nxt.pic[sx*N+sy],nxt.pic[tx*N+ty]);
		nxt.space=tx*N+ty;
		nxt.path++;
		if(dfs(dep+1,i,nxt)){
			return true;
		}
	}
	return false;	
}
int iterative(Puz in){
	for(lim=in.MD;lim<=LIMIT;lim++){
		if(dfs(0,-10,in)){
			printf("%d\n",ans);
			return 0;
		}
	}	
}
int main(){
	Puz src;
	int sum=0;
	for(int i=0;i<NN;i++){
		for(int j=0;j<NN;j++){
			MDT[i][j]=fabs(i/N-j/N)+fabs(i%N-j%N);
		}
	}
	for(int i=0;i<NN;i++){
		scanf("%d",&src.pic[i]);
		if(src.pic[i]==0){
			src.pic[i]=NN;
			src.space=i;
		}
		if(src.pic[i]!=NN)
			sum+=MDT[i][src.pic[i]-1];
	}	
	src.path=0;
	src.MD=sum;
	iterative(src);
	
}