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;

int cnts = 0;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int t[4][4];
int dst[4][4][16];
bool flag = false;

void init() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) t[i][j] = 4 * (i * 4 + j);
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 1; k < 16; k++) {
				int sx = (((k + 15) % 16) / 4), sy = (((k + 15) % 16) % 4);
				dst[i][j][k] = abs(i - sx) + abs(j - sy);
			}
		}
	}
}

bool dfs(int dep, unsigned long long V, int px, int py, int prevdir, int exp) {
	if (flag == true) return true;
	if (dep == 0) {
		flag = true;
		return true;
	}

	for (int i = 0; i < 4; i++) {
		int sx = px + dx[i], sy = py + dy[i];
		if (sx < 0 || sy < 0 || sx > 3 || sy > 3) continue;
		if (((i + 2) & 3) == prevdir) continue;

		unsigned long long V1 = ((V >> t[px][py]) & 15ULL);
		unsigned long long V2 = ((V >> t[sx][sy]) & 15ULL);
		int nexExp = exp - dst[px][py][V1] - dst[sx][sy][V2] + dst[px][py][V2] + dst[sx][sy][V1];
		if (nexExp > dep - 1) continue;

		unsigned long long nexV = V + ((V2 - V1) << t[px][py]) + ((V1 - V2) << t[sx][sy]);
		bool ret = dfs(dep - 1, nexV, sx, sy, i, nexExp);
		if (ret == true) return true;
	}
	return false;
}

int main() {
	// 初期値
	unsigned long long InitV = 0;
	int Initpx, Initpy, Initexp = 0;

	// 入力
	init();
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			unsigned long long pv; cin >> pv;
			InitV += (pv << t[i][j]);
			if (pv != 0) Initexp += dst[i][j][pv];
			if (pv == 0) { Initpx = i; Initpy = j; }
		}
	}
	if (Initexp == 0) {
		cout << "0" << endl;
		return 0;
	}

	// 探索
	for (int i = 1; i <= 80; i++) {
		bool I = dfs(i, InitV, Initpx, Initpy, -1, Initexp);
		if (I == true) { cout << i << endl; break; }
	}
	return 0;
}