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 <map>
#include <queue>
#include <iostream>
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, dist[16][16], goals[16], goals2[16]; ull s, goal = 1147797409030816545;
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 = 0;
	for (int i = 0; i < 16; i++) {
		int ww = ((s >> (i * 4)) & 15);
		if (!ww) continue;
		for (int j = 0; j < 16; j++) {
			if (ww == goals[j]) {
				rr += dist[i][j];
			}
		}
	}
	for (int level = rr; ; level++) {
		queue<state> que;
		que.push(state{ s, zz, -99, 0, rr });
		while (!que.empty()) {
			state a = que.front(); que.pop();
			ull v = a.x; int z = a.zero;
			int dir[4] = { 1, 0, -1, 0 };
			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 = a.remain;
					xx -= dist[e][goals2[g]];
					xx += dist[z][goals2[g]];
					if (w == goal) return a.dist + 1;
					if (a.dist + xx + 1 <= level) 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 < 15; i++) goals[i] = i + 1; goals[15] = 0;
	for (int i = 0; i < 16; i++) goals2[goals[i]] = i;
	for (int i = 0; i < 16; i++) {
		cin >> a;
		s += ((1ULL * a) << (i * 4));
	}
	cout << solve() << endl;
	return 0;
}