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;
const int LIMIT=45;
int limit;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct point{
    int x,y;
};
struct puzzle{
    int f[4][4];
    point p[16];
    point zero;
};
puzzle aim,in;
void init()
{
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=4*i+j+1;
        if(num==16) continue;
        aim.f[i][j]=num;
        aim.p[num].x=i,aim.p[num].y=j;
    }
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=in.f[i][j];
        if(num==0) {in.zero.x=i;in.zero.y=j;continue;}
        in.p[num].x=i,in.p[num].y=j;
     } 
}
int exp(puzzle a)
{
    int t=0;
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
    {
        int num=a.f[i][j];
        if(num==0) continue;
        t+=abs(i-aim.p[num].x)+abs(j-aim.p[num].y);
    }
    return t;
}
bool dfs(puzzle t,int step,int di)
{
    int e=exp(t);
    if(step+e>limit) return false;
    if(e==0) return true;
    for(int i=0;i<4;i++)
    {
        puzzle tmp=t;
        int x=tmp.zero.x,y=tmp.zero.y;
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>3||tx<0||ty>3||ty<0) continue;
        if(max(di,i)-min(di,i)==2) continue;
        swap(tmp.zero,tmp.p[tmp.f[tx][ty]]);
        swap(tmp.f[x][y],tmp.f[tx][ty]);
        if(dfs(tmp,step+1,i)) return true;
    }
    return false;
}
int iterative_deepening()
{
    init();
    for(limit=exp(in);limit<=LIMIT;limit++)
    if(dfs(in,0,-100)) return limit;
}
int main()
{
    for(int i=0;i<4;i++)
    for(int j=0;j<4;j++) cin>>in.f[i][j];
    cout<<iterative_deepening()<<endl;
    return 0;
}