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 <stdio.h>
#include <stdlib.h>
#define N 4
 
int map[N][N];
int risou[N][N];

int x0,y0;
int lim;
bool check(void){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]!=risou[i][j]) return false;
        }
    }
    return true;
}

int heuris(){
	int res=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(map[i][j]!=0)res += abs(i-(map[i][j]-1)/N)+abs(j-(map[i][j]-1)%N);
		}
	}
	return res;
}
bool swapping(int x,int y,int dep){
    int temp=map[x0+x][y0+y];
    map[x0+x][y0+y]=map[x0][y0];
    map[x0][y0]=temp;
    x0+=x;
    y0+=y;
    if(check()){
        printf("%d\n",dep);
        exit(0);
        return true;
    }
    if(dep+heuris()<=lim){
        if(x!=1&&x0-1!=-1) swapping(-1,0,dep+1);
        if(x!=-1&&x0+1!=N) swapping(1,0,dep+1);
        if(y!=1&&y0-1!=-1) swapping(0,-1,dep+1);
        if(y!=-1&&y0+1!=N) swapping(0,1,dep+1);
    }
    temp=map[x0-x][y0-y];
    map[x0-x][y0-y]=map[x0][y0];
    map[x0][y0]=temp;
    x0-=x;
    y0-=y;
    return false;
}
int main(void){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
			risou[i][j]=i*N+j+1;
            scanf("%d",&map[i][j]);
            if(map[i][j]==0){
                x0=i;
                y0=j;
            }
        }
    }
	risou[N-1][N-1]=0;

    if(check()){
        printf("0\n");
        return 0;
    }
    for(lim=1;lim<46;lim++){
        if(x0-1!=-1) swapping(-1,0,1);
        if(x0+1!=N) swapping(1,0,1);
        if(y0-1!=-1) swapping(0,-1,1);
        if(y0+1!=N) swapping(0,1,1);
    }
    printf("Unsolved\n");
    return 0;
}