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 <bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
struct state { ull x; int zero, pre, dist, remain; };
bool operator<(const state& s1, const state& s2) { return s1.dist + s1.remain > s2.dist + s2.remain; }
int a, cz, dist[16][16]; ull s, goal = 1147797409030816545;
int goals[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
int goals2[] = { 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
int goals3[] = { 15, 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11 };
int dir[4] = { 1, 0, -1, 0 };
inline int getheuri(ull x) {
	int ret1 = 0; cz++;
	for (int i = 0; i < 16; i++) {
		int ww = ((x >> (i * 4)) & 15);
		if (!ww) continue;
		ret1 += dist[i][goals2[ww]];
	}
	int ret2 = 0, ret3 = 0;
	for (int i = 0; i < 16; i++) {
		for (int j = i + 1; j < 16; j++) {
			int ww1 = ((x >> (i * 4)) & 15);
			int ww2 = ((x >> (j * 4)) & 15);
			if (goals2[ww1] > goals2[ww2]) ret2++;
			if (goals3[ww1] > goals3[ww2]) ret3++;
		}
	}
	ret2 = ret2 / 3 + ret2 % 3;
	ret3 = ret3 / 3 + ret3 % 3;
	int ret = max(ret1, ret2 + ret3);
	return ret1;
}
int solve() {
	if (s == goal) return 0;
	int zz = -1;
	for (int i = 0; i < 16; i++) {
		if (!((s >> (i * 4)) & 15)) zz = i;
	}
	int rr = getheuri(s);
	priority_queue<state> que;
	que.push(state{ s, zz, -99, 0, rr });
	while (!que.empty()) {
		state a = que.top(); que.pop();
		ull v = a.x; int z = a.zero;
		for (int i = 0; i < 4; i++) {
			if (abs(i - a.pre) == 2) continue;
			int dx = dir[i], dy = dir[i ^ 1];
			int e = z + dy * 4 + dx;
			int g = ((v >> (e << 2)) & 15);
			if (0 <= e && e < 16 && (e & 3) - (z & 3) == dx) {
				ull w = v;
				w -= ((1ULL * g) << (e << 2));
				w += ((1ULL * g) << (z << 2));
				int xx = getheuri(w);
				if (w == goal) return a.dist + 1;
				que.push(state{ w, e, i, a.dist + 1, xx });
			}
		}
	}
	return -1;
}
int main() {
	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 16; j++) {
			dist[i][j] = abs((i >> 2) - (j >> 2)) + abs((i & 3) - (j & 3));
		}
	}
	for (int i = 0; i < 16; i++) {
		cin >> a;
		s += ((1ULL * a) << (i * 4));
	}
	cout << solve() << endl;
	return 0;
}