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 <queue>
#include <unordered_set>
#include <algorithm>
#include <iomanip>

const int DEPTH_LIMIT = 45;

using namespace std;

void PrintBoard( const vector<int>& b ) {
    for ( int row=0; row<4; ++row ) {
	for ( int col=0; col<4; ++col ) cout << setw(2) << " " << b[row*4+col];
	cout << endl;
    }
}

bool IsCompleted( const vector<int>& b ) {
    for ( int i=0; i<15; ++i ) {
	if ( b[i] != i+1 ) return false;
    }
    return b[15] == 0;
}

int H1( const vector<int>& b ) {
    int dist = 0;
    for ( int i=0; i<15; ++i ) dist += b[i] == (i+1) ? 1 : 0;
    return dist;
}

int H2( const vector<int>& b ) {
    static int tab[16][2] = {
	{ 3, 3 },//0
	{ 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 },
	{ 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 },
	{ 0, 2 }, { 1, 2 }, { 2, 2 }, { 3, 2 },
	{ 0, 3 }, { 1, 3 }, { 2, 3 } };
	
    int dist = 0;
    for ( int i=0; i<16; ++i ) {
	if ( b[i] == 0 ) continue;//ignore pos of 0
	int x = i%4;
	int y = i/4;
	dist += abs( tab[b[i]][0] - x ) + abs( tab[b[i]][1] - y );
    }
    return dist;
}

const int dx[4] = { -1, 0, 1,  0 };
const int dy[4] = {  0, 1, 0, -1 };
vector<int> board, board_org( 16 );
    
bool Solve( int x, int y, int curr, int lim, int prev ) {

    if ( IsCompleted( board ) ) return true;

    //    cout << "--- " << x << " " << y << " " << curr << " " << lim << endl;
    //    PrintBoard( board );
    
    if ( curr == lim ) return false;
    
    for ( int i=0; i<4; ++i ) {

	if ( (i+2)%4 == prev ) continue;
	
	int nx = x + dx[i];
	int ny = y + dy[i];

	if ( nx < 0 || nx > 3 || ny < 0 || ny > 3 ) continue;

	swap( board[4*y+x], board[4*ny+nx] );
	
	//	cout << "i = " << i << " " << curr + H2( board ) << endl;
	//	PrintBoard( board );
	
	if ( curr + H2( board ) > lim ) {
	    swap( board[4*y+x], board[4*ny+nx] );
	    continue;
	}

	if ( Solve( nx, ny, curr+1, lim, i ) ) return true;

	swap( board[4*y+x], board[4*ny+nx] );	
    }

    return false;
}

int main() {

    int x, y;
    
    for ( int i=0; i<4; ++i ) {
	for ( int j=0; j<4; ++j ) {
	    cin >> board_org[i*4+j];
	    if ( board_org[i*4+j] == 0 ) {
		x = j;
		y = i;
	    }
	}
    }

    for ( int d=0; d<DEPTH_LIMIT; ++d ) {
	board = board_org;
	if ( Solve( x, y, 0, d, 5 ) ) {
	    cout << d << endl;
	    return 0;
	}
	//	cout << endl;
    }

    cout << DEPTH_LIMIT << endl;
    
    return 0;
}