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:


#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
bool OOA(int x, int y, int H, int W) { return (0 <= x && x<H) && (0 <= y && y<W); }

int lim,puz[4][4];

int estmd(){
	int ret=0;
	for(int i=0;i<4;i++)for(int j=0;j<4;j++){
		if(puz[i][j] == -1)continue;
		ret+=abs(puz[i][j]/4-i)+abs(puz[i][j]%4-j);
	}
	return ret;
}

bool IDAst(int nc,int bd,int si,int sj){
	int md=estmd();
	if(md==0)return true;
	if(nc+md>lim)return false;
	for(int d=0;d<4;d++){
		int ni=si+dy[d],
			nj=sj+dx[d];
		if(!OOA(nj,ni,4,4)||(abs(d-bd)==2))continue;
		swap(puz[si][sj],puz[ni][nj]);
		if(IDAst(nc+1,d,ni,nj))return true;
		swap(puz[si][sj],puz[ni][nj]);
	}
	return false;
}

int main(){
	int z;
	for(int i=0;i<16;i++){
		cin>>puz[i/4][i%4];
		if(puz[i/4][i%4]==0)z=i;
		puz[i/4][i%4]--;
	}

	for(lim=0;lim<100;lim++){
		if(IDAst(0,10,z/4,z%4)){
			cout<<lim<<endl;
			return 0;
		}
	}
	return 0;
}