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 <cmath>

using namespace std;

const int N = 16;
const int N2 = 4;
const int LIMIT = 100;

typedef struct {
	int M[N];
	int space;
	int MD; 
} Puzzle;

const int dx[4] = {0,-1,0,1};
const int dy[4] = {1,0,-1,0};
const char dir[4] = {'r','u','l','d'};

int MDT[N][N];//曼哈顿距离 

Puzzle state;

int limit;//深度限制

int path[LIMIT];

int getAllMD(Puzzle pz){
	int sum = 0;
	for (int i=0;i<N;i++) {
		if (pz.M[i] == 0) continue; //空格不考虑
		sum += MDT[i][pz.M[i]-1]; 
	}
	return sum;
}

bool dfs(int depth,int prev) { //深度优先搜索 
    if (state.MD == 0) return true; //已经得到解
	
	if (depth + state.MD > limit) return false; //剪枝
	
	int sx = state.space / N2;
	int sy = state.space % N2;
	
	Puzzle tmp;
	
	for (int r=0;r<4;r++) {
		int tx = sx + dx[r];
		int ty = sy + dy[r];
		if (tx < 0 || ty < 0 || tx >= N2 || ty >= N2) continue;
		if (max(prev,r) - min(prev,r) == 2) continue; //避免把空格再移到上一步的位置
		tmp = state;
		
		state.MD -= MDT[tx * N2 + ty][state.M[tx*N2+ty] - 1]; //删除原状态的曼哈顿距离 
		state.MD += MDT[state.space][state.M[tx*N2+ty]-1]; //添加新状态的曼哈顿距离 
		swap(state.M[tx*N2 + ty],state.M[state.space]);
		state.space = tx*N2 + ty;
		if (dfs(depth + 1,r)) {
			path[depth] = r; return true;
		}
		state = tmp; //回溯 
	} 
	return false;
}

//迭代加深 
string iterative_deepening(Puzzle in) {
	in.MD = getAllMD(in);
	
	for (limit = in.MD;limit<= LIMIT;limit++) {
		state = in;
		if (dfs(0,-100)) {
			string ans = "";
			for (int i=0;i<limit;i++) {
				ans += dir[path[i]];
			}
			return ans;
		}
	}
	
	return "unsolvable";
}

int main() {
	for (int i=0;i<N;i++) {
		for (int j=0;j<N;j++) {
			//d(i,j)=|X1-X2|+|Y1-Y2|.，这里竖轴为x，横轴为y 
			MDT[i][j] = abs(i / N2 - j /N2) + abs(i % N2 - j % N2); //计算i到j的曼哈顿距离 
		}
	}
	
	Puzzle in;
	for (int i=0;i<N;i++) {
		cin >> in.M[i];
		if (in.M[i] == 0) {
			in.space = i;
		}
	} 
	string ans = iterative_deepening(in);
	cout << ans.size() << endl;
	return 0;
}