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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_T 50
#define WIDTH 7125
pair<int, vector<vector<int>>> E[MAX_T][WIDTH], D[WIDTH];
vector<vector<int>>X;
int hantei(vector<vector<int>>a) {
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int Num = (a[i][j] + 15) % 16; if (a[i][j] == 0)continue;
			sum += abs(i - (Num / 4)) + abs(j - (Num % 4));
		}
	}
	return sum;
}
int main() {
	for (int i = 0; i < 4; i++) {
		vector<int>FF; for (int j = 0; j < 4; j++) { int p; cin >> p; FF.push_back(p); }
		X.push_back(FF);
	}
	E[0][0] = make_pair(hantei(X), X);
	for (int i = 0; i < MAX_T; i++) {
		int CNT = 0;
		if (E[i][0].first == 0) { cout << i << endl; break; }
		for (int j = 0; j < WIDTH; j++) {
			if (E[i][j].second.size() == 0)break;
			int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
			vector<vector<int>>H = E[i][j].second; int I = E[i][j].first;
			int C = 0;
			for (int k = 0; k < 16; k++) {
				if (H[k / 4][k % 4] == 0) {
					C = k;
				}
			}
			for (int k = 0; k < 4; k++) {
				vector<vector<int>>J = H;
				int Ex = (C / 4) + dx[k], Ey = (C % 4) + dy[k];
				if (Ex < 0 || Ex > 3 || Ey < 0 || Ey > 3)continue;
				swap(J[C / 4][C % 4], J[Ex][Ey]);
				D[CNT] = make_pair(hantei(J), J); CNT++;
			}
		}
		sort(D, D + CNT); E[i + 1][0] = D[0]; int cnt2 = 1;
		for (int k = 1; k < CNT; k++) {
			if (D[k - 1] == D[k])continue;
			E[i + 1][cnt2] = D[k]; cnt2++;
		}
	}
	return 0;
}