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;
//mit全部的曼哈顿距离之和
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)//sx,sy是空格的位置
{
    if(flag) return;
    int dv=hv(map);
    if(len==limit)
    {
        if(dv==0)  //成功 退出
        {
            flag=1;
            length=len;
            return;
        }
        else return;  //超过预设长度 回退
    }
    else if(len<limit)
    {
        if(dv==0)  //短于预设长度 成功 退出
        {
            flag=1;
            length=len;
            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++) //map一维map2二维
        {
            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)//要求45步之内到达
        {
            dfs(x1,y1,0,0);
            if(flag==0) limit++; //得到的是最小步数
        }
        if(flag) printf("%d\n",length);
    }
    return 0;
}