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 dx[] = {0,-1,0,1};
static const int dy[] = {1,0,-1,0};
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;
    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;
}

inline void dump(Puzzle& u) {
    for(int i=0; i<N; i++) {
	for(int j=0; j<N; j++)
	    cout << u.f[i*N+j] << " " ;
	cout << endl;
    }
}
map<Puzzle, bool> V;

int astar(Puzzle s) {
    priority_queue<State> PQ;
    s.MD = getAllMD(s);
    s.cost = 0;
    Puzzle u,v;
    State initial;
    initial.puzzle = s;
    initial.estimated = getAllMD(s);
    PQ.push(initial);

    while( !PQ.empty() ) {
	State st = PQ.top(); PQ.pop();
	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 or ty<0 or tx>=N or ty>=N ) continue;
	    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;
		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++) {
	cin >> in.f[i];
	if(in.f[i] == 0) {
	    in.f[i] = N2;
	    in.space = i;
	}
    }
    cout << astar(in) << endl;
    return 0;
}