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:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int num = 16, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 4;
const char wa[] = { 'u', 'l', 'd', 'r' };
int md[num][num];
vector<int> way;
int lm;
struct puzzle {
	int sp, p[num], mdp;
	string way;
	bool operator < (const puzzle &pu) const {
		for (int i = 0; i < num; i++) {
			if (p[i] == pu.p[i]) continue;
			return p[i] < pu.p[i];
		}
		return false;
	}
};
puzzle pu;
/*bool dfs(int de, int prev, puzzle pu) {
	if (pu.mdp + de> lm) return false;
	//cout << "prev" << prev << "pu.sp" << pu.sp << "mdp" <<  pu.mdp << endl;
	if (!pu.mdp) {return true; }
	int sx = pu.sp / nd;
	int sy = pu.sp % nd;
	int tx, ty, ns;
	//puzzle tmp = pu;
	puzzle tmp;
	for (int r = 0; r < nd; r++) {
		if (max(r, prev) - min(r, prev) == 2) continue;
		tx = sx + ud[r];
		ty = sy + lr[r];
		tmp = pu;
		if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
		ns = tx * nd + ty;
		pu.mdp = pu.mdp - md[ns][pu.p[ns]-1] + md[sx*nd + sy][pu.p[ns]-1];
		pu.sp = ns;
		swap(pu.p[ns], pu.p[pu.sp]);
		if (dfs(de + 1, r, pu)) { 
			cout << "r" << r << "sp" << pu.sp << endl;
			way.push_back(r);
			return true; 
		}
		pu = tmp;
	}
	return false;
}*/
bool dfs(int de, int pr) {
	if (de + pu.mdp > lm) return false;
	if (pu.mdp == 0) return true;
	int sx = pu.sp / nd;
	int sy = pu.sp % nd;
	int tx, ty, ns;
	puzzle tmp;
	for (int r = 0; r < nd; r++) {
		if (max(r, pr) - min(r, pr) == 2) continue;
		tx = sx + ud[r];
		ty = sy + lr[r];
		tmp = pu;
		if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
		ns = tx * nd + ty;
		pu.mdp -= md[ns][pu.p[ns]- 1];
		pu.mdp += md[pu.sp][pu.p[ns] - 1];
		pu.sp = ns;
		swap(pu.p[ns], pu.p[sx * nd + sy]);
		if (dfs(de + 1, r)) {
			way.push_back(r);
			return true;
		}
		pu = tmp;
	}
	return false;
}

int main() {
	puzzle p;
	int sum = 0;
	for (int i = 0; i < num; i++) {
		cin >> p.p[i];
		if (!p.p[i]) { p.sp = i; p.p[i] = num; }
	}
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			md[i][j] = abs(i / nd - j / nd) + abs(i%nd - j%nd);
	for (int i = 0; i < num; i++) {
		if (p.p[i] == num) continue;
		sum += md[i][p.p[i] - 1];
	}
	p.mdp = sum;
	pu = p;
	for (lm = p.mdp; lm < 100; lm++) {
		if (dfs(0, -5/*, pu*/)) {
			cout << way.size() << endl; return 0;
		}
	}
}