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 <cstdio>
#include <cmath>
#include <map>
#include <queue>

using namespace std;

#define N (4)
#define N2 (N * N)

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r', 'u', 'l', 'd'};
int MDT[N2][N2];

struct Puzzle {
    int f[N2], space, MD;
    int cost;
    
    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 puzzle;
    int estimated;

    // priority_queue????????????????????§?????§??????????????????
    // ????°????????????????????????????????????????????????±????????????????????????????????¨????????????
    bool operator < ( const State &s ) const {
	return estimated > s.estimated;
    }
};

int getAllMD( Puzzle pz ) {
    int sum = 0;
    for ( int i = 0; i < N2; i++ ) {
	if ( pz.f[i] == N2 ) continue;
	sum += MDT[i][pz.f[i] - 1];
    }

    return sum;
}

int astar( Puzzle s ) {
    priority_queue<State> PQ;
    s.MD = getAllMD( s );
    s.cost = 0;
    map<Puzzle, bool> V;
    State initial;
    initial.puzzle = s;
    initial.estimated = getAllMD( s );
    V[s] = true;
    PQ.push( initial );

    while ( !PQ.empty() ) {
	State st = PQ.top(); PQ.pop();
	Puzzle u = st.puzzle;

	if ( u.MD == 0 ) return u.cost;
//	V[u] = true;
	
	int sx = u.space / N;
	int sy = u.space % N;
	
	for ( int r = 0; r < 4; r++ ) {
	    int tx = sx + dx[r];
	    int ty = sy + dy[r];
	    
	    if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
	    Puzzle v = u;
	    
	    v.MD -= MDT[tx * N + ty][v.f[tx * N + ty] - 1];
	    v.MD += MDT[sx * N + sy][v.f[tx * N + ty] - 1];
	    
	    swap( v.f[sx * N + sy], v.f[tx * N + ty] );
	    v.space = tx * N +ty;

	    if ( !V[v] ) {

		v.cost++;
		State news;
		news.puzzle = v;
		news.estimated = v.cost + v.MD;
		V[v] = true;
		PQ.push( news );
	    }
	}
    }

    return -1;
}


int main()
{
    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 ) );
	}
    }

    Puzzle in;
    
    for ( int i = 0; i < N2; i++ ) {
	scanf("%d", &in.f[i]);
	if ( in.f[i] == 0 ) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }

    int ans = astar( in );
    
    if ( ans != -1 ) {
	printf("%d\n", ans);
    }

    return 0;
}