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>
#define N 4
using namespace std;
int m[N][N];
int p[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

bool legal(int r1, int c1){
	return (r1>=0 && r1<N && c1>=0 && c1<N);
}
int cost(){
	int ans = 0, x;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++){
			if(!m[i][j]) continue;
			x = m[i][j] - 1;
			ans += abs(x/N-i) + abs(x%N-j);
		}
	return ans;
}
bool dfs(int limit, int back, int now, int r, int c){
	int predict = cost();
	int r1, c1;
	if(predict == 0) return 1;
	if(predict+now > limit) return 0;
	for(int i=0; i<4; i++){
		r1 = p[i][0] + r;
		c1 = p[i][1] + c;
		if(!legal(r1, c1)) continue;
		if(abs(back-i) == 2) continue;
		swap(m[r][c], m[r1][c1]);
		if(dfs(limit, i, now+1, r1, c1)) return 1;
		swap(m[r][c], m[r1][c1]);
	}
	return 0;
}
int main()
{	
	int r, c;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++){
			cin >> m[i][j];
			if(m[i][j] == 0) r = i, c = j;
		}
	for(int limit=0; ; limit++){
		if( dfs(limit, 99, 0, r, c) ){
			cout << limit <<endl;
			break;
		}
	}
	return 0;
}