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 dir[4] = { 1, 0, -1, 0 };
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];
			}
		}
	}
	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 = a.remain;
				xx -= dist[e][goals2[g]];
				xx += dist[z][goals2[g]];
				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 < 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;
}