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>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,ull> P;
typedef pair<int,int>Pii;
#define F first
#define S second
 
 
int dep=0;;
int X[]={0,3,2,1,0,3,2,1,0,3,2,1,0,3,2,1};
int Y[]={0,3,3,3,3,2,2,2,2,1,1,1,1,0,0,0};
int dy[]={1,0,-1,0};
int dx[]={0,-1,0,1};
ull mask[4][4],bit[4][4];

const int MAX = 5000;
ull G=1311768467463790320 , x , s , M=-1;

Pii pos(ull A){
    r(y,4)r(x,4){
        if(!((A>>bit[y][x])&15)){
            return Pii(y,x);
        }
    }

}

int cost(ull A){
	int sum=0;
	r(y,4){
        r(x,4){
            int k=((A>>bit[y][x])&15);
            if(!k)continue;
    		sum += abs(X[k]-x) + abs(Y[k]-y);
        }
	}
	return sum;
}

signed main(){

    ull init = 0;
    unordered_set<ull>st;

    for(int i=3;i>=0;i--){
        for(int j=3;j>=0;j--){
            ull x;
            cin>>x;
            init|=(x<<((i*4+j)*4));
            mask[i][j] = (ull)15<<((i*4+j)*4);
            bit[i][j] = (i*4+j)*4;
        }
    }


    priority_queue<P> Q[2];
    Q[0].push(P(cost(init),init));
    st.insert(init);
 
    while( !Q[dep%2].empty() ){
        while( !Q[dep%2].empty() ){
            P A=Q[dep%2].top(); Q[dep%2].pop();

            if(A.S==G){
                cout<<dep<<endl;
                return 0;
            }

            Pii p=pos(A.S);
            int x=p.S, y=p.F;
            ull a = (A.S>>bit[y][x])&15;

            r(i,4){
            	int ny=p.F+dy[i];
            	int nx=p.S+dx[i];
            	if( ny<0 || nx<0 || 4<=ny || 4<=nx ) continue;

                ull b = ( A.S>>bit[ny][nx] )&15;
                ull c = ( A.S & ( M - mask[y][x] - mask[ny][nx] ) );
                ull nex = (c | ( b<<bit[y][x] ) | ( a<<bit[ny][nx] ) );

                if(st.count(nex)) continue;
                st.insert(nex);
                Q[(dep+1)%2].push(P(cost(nex),nex));
                if(Q[(dep+1)%2].size()>=MAX) Q[(dep+1)%2].pop();

            }
        }
        if(dep>=49)break;
        dep++;
    }
    
}