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<math.h>  
#include<algorithm>
using namespace std;
 
int nx[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
 

int goal[16][2]= {{3,3},{0,0},{0,1},{0,2},//0 1 2 3
				  {0,3},{1,0},{1,1},{1,2},//4 5 6 7
				  {1,3},{2,0},{2,1},{2,2},//8 9 10 11
				  {2,3},{3,0},{3,1},{3,2}};//12 13 14 15
				  
int map[4][4],map2[16],limit;
int flag,length;				  
      
int hv(int a[][4])
{
    int cost=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)  
        {
            int w=map[i][j];
            if(w!=0) cost+=abs(i-goal[w][0])+abs(j-goal[w][1]);
        }
    }
    return cost;
}
 
void dfs(int x,int y,int len,int pre_move)
{
    if(flag) return;
    int dv=hv(map);
    if(len==limit)
    {
        if(dv==0) 
        {
            flag=1;
            length=len;
            return;
        }
        else return; 
    }
 
    for(int i=0;i<4;i++)  
    {
        if(i+pre_move==3&&len>0) continue;
        int tx=x+nx[i][0];
        int ty=y+nx[i][1];
        if(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            swap(map[x][y],map[tx][ty]);
            int p=hv(map);
            if(p+len<=limit&&flag==0)
            {
                dfs(tx,ty,len+1,i);
                if(flag) return;
            }
            swap(map[x][y],map[tx][ty]);
        }
    }
}
 
int main()  
{
    int t=1;
    while(t--)       
    {
		int x1,y1;
        for(int i=0;i<16;i++)
        {
            scanf("%d",&map2[i]);
            if(map2[i]==0)
            {
                x1=i/4;
				y1=i%4;
				map[x1][y1]=0;
            }
            else
            {
                map[i/4][i%4]=map2[i];
            }
        }                                      
 
        limit=hv(map);
        //printf("limit===%d\n",limit);
        flag=0;
        length=0;
        while(flag==0&&length<=45)
        {
            dfs(x1,y1,0,0);
            if(flag==0) limit++; 
        }
        if(flag) printf("%d\n",length);
    }
    return 0;
}