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>
using namespace std;

const int N = 4;
const int D_y[4] = { 1,0,-1,0 };
const int D_x[4] = { 0,1,0,-1 };

int ANS[N][N] = { {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0} };
int ans_x[N * N] = { 0 };
int ans_y[N * N] = { 0 };

bool eq(int p1[N][N], int p2[N][N]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (p1[i][j] != p2[i][j])return false;
		}
	}
	return true;
}

int step(int puzzle[N][N]) {
	int n = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (puzzle[i][j] == 0)continue;
			int x = ans_x[puzzle[i][j]] - j;
			int y = ans_y[puzzle[i][j]] - i;
			x = x < 0 ? -x : x;
			y = y < 0 ? -y : y;
			n += x + y;
		}
	}
	return n;
}

bool search(int puzzle[N][N], int x,int y, int px, int py, int depth, int lim) {
	if (depth + step(puzzle) > lim)return false;
	if (eq(ANS, puzzle))return true;
	for (int i = 0; i < 4; i++) {
		int X = x + D_x[i];
		int Y = y + D_y[i];
		if ((X == px && Y == py) || X < 0 || Y < 0 || X >= N || Y >= N)continue;
		swap(puzzle[y][x], puzzle[Y][X]);
		if (search(puzzle, X, Y, x, y, depth + 1, lim))return true;
		swap(puzzle[y][x], puzzle[Y][X]);
	}
	return false;
}

int solve() {
	int puzzle[N][N];
	int x, y;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> puzzle[i][j];
			if (puzzle[i][j] == 0) {
				x = j;
				y = i;
			}
		}
	}
	for (int i = 0; i < 45; i++) {
		if (search(puzzle, x, y, -1, -1, 0, i)) {
			return i;
		}
	}
	return 45;
}

int main() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans_x[ANS[i][j]] = j;
			ans_y[ANS[i][j]] = i;
		}
	}
	cout << solve() << endl;
	return 0;
}