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 <math.h>
#include <algorithm>
using namespace std;

int d_x[4] = { -1,0,1,0 };
int d_y[4] = { 0,1,0,-1 };

int t[4][4];
int level = 0;

int countpath() {
	int ret = 0;
	int tmp;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (t[i][j] != 0) {
				tmp = t[i][j] - 1;
				ret += abs(tmp / 4 - i) + abs(tmp % 4 - j);
			}
		}
	}
	return ret;
}

bool check(int depth, int pre, int px, int py) {
	int w = countpath();
	if (w + depth > level) return false;
	if (w == 0)return true;
	int dx, dy;
	for (int i = 0; i < 4; i++) {
		if (abs(i - pre) != 2) {
			dx = px + d_x[i];
			dy = py + d_y[i];
			if (dx < 0 || dx == 4 || dy < 0 || dy == 4) continue;
			swap(t[dx][dy], t[px][py]);
			if (check(depth + 1, i, dx, dy)) return true;
			swap(t[dx][dy], t[px][py]);
		}

	}
	return false;
}

void solution(int px, int py) {
	for (level = 0;; level++) {
		if (check(0, 9, px, py)) {
			cout << level << endl;
			return;
		}
	}
}

int main() {
	int px, py;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> t[i][j];
			if (t[i][j] == 0) {
				px = i;
				py = j;
			}
		}
	}
	solution(px, py);
	return 0;
}