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>
using namespace std;
using i32 = int_fast32_t;

i32 ans = -1;
i32 d[4] = {-4, -1, 1, 4};
i32 mdt[16][16];
i32 limit;
string S;
i32 md, space;

inline i32 getAllMD()
{
	i32 sum = 0;
	for ( i32 i = 0; i < 16; i++ ) {
		if ( S[i] == 'a' ) continue;
		sum += mdt[i][S[i] - 'b'];
	};
	return (sum);
}

void dfs(i32 n, i32 prev) {
	if ( md == 0 ) { ans = n; return; }
	if ( md + n > limit ) return;

	for ( i32 i = 0; i < 4; i++ ) {
		i32 npos = space + d[i];
		if ( i == 1 && (space & 3) == 0 ) continue;
		if ( i == 2 && (space & 3) == 3 ) continue;
		if ( npos < 0 || 15 < npos ) continue;
		if (prev == npos) continue;

		i32 tmd = md;

		md -= mdt[npos][S[npos] - 'b'];
		md += mdt[space][S[npos] - 'b'];
		swap(S[space], S[npos]);
		space^=npos^=space^=npos;
		dfs(n + 1, npos);
		if ( ans != -1 ) return;
		md = tmd;
		space^=npos^=space^=npos;
		swap(S[space], S[npos]);
	}
}

int main() {
	for ( i32 i = 0; i < 16; i++ ) {
		i32 c;
		cin >> c;
		S += c + 'a';
	}

	for ( i32 i = 0; i < 16; i++ ) {
		for ( i32 j = 0; j < 16; j++ ) {
			mdt[i][j] = abs(i / 4 - j / 4) + abs(i % 4 - j % 4);
		}
	}

	md = getAllMD();
	space = S.find('a');
	for ( limit = md; limit <= 1000; limit++ ) {
		dfs(0, -1);
		if ( ans != -1 ) { cout << ans << endl; return (0); }
	}
}