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;

static const int N = 4;
static const int N2 = 16;
static const int LIMIT = 100;

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


struct Puzzle {
    int f[N2], space, MD;
};


Puzzle state;
int limit; // ??±????????¶???
int path[LIMIT];

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;
}

bool isSolved(){
    for(int i=0; i<N2; i++)
	if( state.f[i] != i+1)
	    return false;
    return true;
}

bool DFS(int depth, int prev) {

    if( state.MD == 0 ) return true;
    if( depth + state.MD > limit ) return false; // ??±?????¶???OUT

    int sx = state.space / N;
    int sy = state.space % N;
    Puzzle tmp;
    for(int r=0; r<4; r++) {
	int tx = sx + dx[r];
	int ty = sy + dy[r];
	if( tx<0 or ty<0 or tx>=N or ty>=N ) continue;
	if( max(prev,r) - min(prev,r) == 2 ) continue;
	tmp = state;
	state.MD -= MDT[tx*N+ty][state.f[tx*N+ty]-1];
	state.MD += MDT[sx*N+sy][state.f[tx*N+ty]-1];
	swap(state.f[sx*N+sy], state.f[tx*N+ty]);
	state.space = tx*N+ty;

	if( DFS(depth+1, r) ) {
	    path[depth] = r;
	    return true;
	}
	state = tmp;
    }
    return false;	    
}

string iterative_deeping(Puzzle in) {
    in.MD = getAllMD(in);

    for(limit = in.MD; limit <=LIMIT; limit++) {
	state = in;
	if( DFS(0,-100) ) {
	    string ans = "";
	    for(int i=0; i<limit; i++)
		ans += dir[path[i]];
	    return ans;
	}
    }
    return "unsolvable";
}

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++) {
	cin >> in.f[i];
	if(in.f[i] == 0) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }
    string ans = iterative_deeping(in);
    cout << ans.size() << endl;
    
    return 0;
}