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;

#define N 4
#define N2 16

struct puzzle {
	int f[N2];
	int space;
	int depth;
	int MD;
	puzzle() { depth = 0; }
	bool operator <( const puzzle p ) const
	{
		for( int i = 0; i < N2; i++ ) {
			if( f[i] == p.f[i] ) continue;
			return f[i] < p.f[i];
		}
		return false;
	}
};

struct state {
	puzzle p;
	int score;
	bool operator >( const state s ) const
	{
		return score > s.score;
	}
};

int MDT[N2][N2];

int getSum( puzzle x )
{
	int sum = 0;
	for( int i = 0; i < N2; i++ ) {
		if( x.f[i] == N2 ) continue;
		sum += MDT[i][x.f[i] - 1];
	}
	return sum;
}

int main()
{
	puzzle sp;
	for( int i = 0; i < N2; i++ ) {
		cin >> sp.f[i];
		if( sp.f[i] == 0 ) {
			sp.space = i;
			sp.f[i] = N2;
		}
	}

	for( int i = 0; i < N2; i++ ) {
		for( int j = 0; j < N2; j++ ) {
			MDT[i][j] = abs( i / N - j / N ) + abs( i % N - j % N );
		}
	}
	state s;
	sp.MD = getSum( sp );
	s.p = sp;
	s.score = sp.MD;
	int dirh[] = { 0, 0, -1, 1 };
	int dirv[] = { -1, 1, 0, 0 };
	priority_queue<state, vector<state>, greater<state> > que;
	map<puzzle, int> m;
	que.push( s );
	int ans = 0;
	while( !que.empty() ) {
		state ts = que.top();
		que.pop();
		puzzle tp = ts.p;
		if( tp.MD == 0 ) {
			ans = tp.depth;
			break;
		}
		m[tp] = 1;
		int sy = tp.space / N;
		int sx = tp.space % N;
		for( int i = 0; i < 4; i++ ) {
			int nx = sx + dirh[i];
			int ny = sy + dirv[i];
			if( nx < 0 || N <= nx || ny < 0 || N <= ny ) continue;
			int ni = ny * N + nx;
			puzzle v = tp;
			v.MD -= MDT[ni][v.f[ni] - 1];
			v.MD += MDT[tp.space][v.f[ni] - 1];
			swap( v.f[ni], v.f[v.space] );
			v.space = ni;
			if( m.find( v ) == m.end() ) {
				v.depth++;
				state news;
				news.p = v;
				news.score = v.MD + v.depth;
				que.push( news );
			}
		}
	}

	cout << ans << endl;
}