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

int x[4] = { -1,0,1,0 };
int y[4] = { 0,1,0,-1 };
int g[4][4];
int m = 0;

bool solve(int dee, int t, int zx, int zy) {
	int c = 0;
	for (int i=0;i<4;i++) {
		for (int j=0;j<4;j++) {
			if (g[i][j] != 0) {
				int t = g[i][j]-1;
				c += abs(t / 4 - i) + abs(t % 4 - j);
			}
		}
	}

	if (c+dee>m) return false;
	if (c==0) return true;
	int dx,dy;
	for(int i=0;i<4;i++) {
		if (abs(i-t)!=2) {
			dx = zx+x[i];
			dy = zy+y[i];
			if (dx < 0 || dx == 4 || dy < 0 || dy == 4) continue;
            swap(g[dx][dy], g[zx][zy]);
            if (solve(dee + 1, i, dx, dy)) return true;
            swap(g[dx][dy], g[zx][zy]);

		}
	}
	return false;
}

int main() {
	int zx,zy;
	for (int i=0;i<4;i++) {
		for (int j=0;j<4;j++) {
			cin>>g[i][j];
			if (g[i][j]==0) {
				zx=i;zy=j;
			}
		}
	}
	for (m=0;m>=0;m++) {
		if (solve(0,9,zx,zy)) {
			cout<<m<<endl;
			return 0;
		}
	}


	return 0;
}