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:
//?????????????§£??????????????§IDA*?????????
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;

typedef vector<int> Board;

const int INF=INT_MAX/3;
int dist[16][16];
Board goal(16);

int heuristic(Board &b){
	int S=0;
	for(int i=0;i<16;i++){
		if(b[i]!=0){
			S=S+dist[i][b[i]-1];
		}
	}
	return S;
}

void Adj(Board &u, vector<Board> &adj){
	int zero;
	for(int i=0;i<16;i++){
		if(u[i]==0){zero=i;}
	}

	if(zero<12){
		Board v(16);
		v=u;
		swap(v[zero],v[zero+4]);
		adj.push_back(v);
	}
	if(zero>3){
		Board v(16);
		v=u;
		swap(v[zero],v[zero-4]);
		adj.push_back(v);
	}
	if(zero%4 == 0 || zero%4 == 1 || zero%4 == 2){
		Board  v(16);
		v=u;
		swap(v[zero],v[zero+1]);
		adj.push_back(v);
	}
	if(zero%4 == 1 || zero%4 == 2 ||zero%4 == 3){
		Board v(16);
		v=u;
		swap(v[zero],v[zero-1]);
		adj.push_back(v);
	}
}

bool DLS(Board &b,Board &prev, int limit,int depth){
	if(b == goal){
		return true;
	}
	if(depth+heuristic(b)<=limit){
		vector<Board> adj;
		Adj(b,adj);
		for(int i=0;i<adj.size();i++){
			if(prev==adj[i]) continue;
			if(DLS(adj[i], b, limit, depth+1)==true){
				return true;
			}
		}
	}
	return false;
}

int IDDFS(Board &init){
	for (int limit=0; ; limit++){
		bool found = DLS(init,init, limit,0);
		if(found){
			return limit;
		}
	}
}

int main(){
	Board init(16);

	for(int i=0;i<16;i++){
		cin >> init[i] ;
	}

	/*
	int x[16]={1,6,7,2,5,10,12,3,0,14,13,8,9,15,11,4};
	for(int i=0;i<16;i++){
		init[i]=x[i]; 
	} 
	*/

	for(int i=0;i<15;i++){
		goal[i]=i+1; 
	}
	goal[15]=0;

	for(int i=0;i<16;i++){
		for (int j=0;j<16;j++){
			dist[i][j]=abs((i/4)-(j/4))+abs((i%4)-(j%4));
		}
	}

	cout << IDDFS(init) << endl;
	return 0;
}