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<string.h>
#include<algorithm>
using namespace std;
#include<stdlib.h>
#define ll long long
const int Max = 4;

int a[4][2] = {0,-1,1,0,-1,0,0,1};
int goal[16][2]= {{3,3},{0,0},{0,1},{0,2},{0,3},{1,0},{1,1},{1,2},{1,3},{2,0},{2,1},{2,2},{2,3},{3,0},{3,1},{3,2}};
int mpp[Max][Max],mpp2[Max*Max];

int flag = 0,limit,Mi;
int ddd()
{
    int i,j;
    int sum = 0;
    for(i = 0; i<4; i++)
    {
        for(j = 0; j<4; j++)
        {
            if( mpp[i][j]!=0 )
                sum += abs(i-goal[mpp[i][j]][0])+abs(j - goal[mpp[i][j]][1]);
        }
    }
    return sum;
}

void dfs(int x,int y,int len,int f)
{
    int d = ddd();
    if(flag) return;
    if(len==limit)
    {
        if(d==0)
        {
            flag = 1;
            Mi = len;
            return ;
        }
        return;
    }

    for(int i = 0; i<4; i++)
    {
        int tx = x + a[i][0];
        int ty = y + a[i][1];
        if(tx>=0&&ty>=0&&ty<4&&tx<4 && (i+f)!=3 )
        {
            swap(mpp[x][y],mpp[tx][ty]);
            if(len+ddd()<=limit)
            {
                dfs(tx,ty,len+1,i);
                if(flag) return ;
            }
            swap(mpp[x][y],mpp[tx][ty]);
        }
    }
}
int main()
{
    int i,j;
    while(~scanf("%d",&mpp[0][0]))
    {
        int y,x;
        if(mpp[0][0]==0)
        {
            y = 0;
            x = 0;
        }
        for(i = 0; i<4; i++)
        {
            for((i==0)?j=1:j=0; j<4; j++)
            {
                scanf("%d",&mpp[i][j]);
                if(mpp[i][j]==0)
                {
                    x = i;
                    y = j;
                }
            }
        }
        /*for(i = 0;i<4;i++)
        {
        	for(j=0;j<4;j++)
        	{
        		printf("%d ",mpp[i][j]);
        	}
        	printf("\n");
        }*/
        flag = 0;
        limit = ddd();
//        printf("<<<<%d\n",limit);
        while(!flag)
        {
            dfs(x,y,0,-1);
                limit ++;
        }
        if(flag)
            printf("%d\n",Mi);
    }
    return 0;
}