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 H=4,W=4;
const int SIZE=H*W;

class State
{
 public:
    string str;
    int space,distFromS,distToG;
    State(string str,int space,int dist):str(str),space(space),distFromS(dist),distToG(0){
        for(int i=0;i<SIZE;i++) if(i!=space){
            int y=i/W,x=i%W;
            int gy=(str[i]-'a')/W,gx=(str[i]-'a')%W;
            distToG+=abs(y-gy)+abs(x-gx);
        }
    }
    bool operator<(const State& s) const{
        return distFromS+distToG>s.distFromS+s.distToG;
    }
};

int d[4]={W,1,-1,-W};

int main()
{  
    string s(SIZE,' '),goal(SIZE,' ');
    for(int i=0;i<SIZE;i++) goal[i]=(char)('a'+i);
    for(int i=0;i<SIZE;i++){
        int t; cin>>t;
        if(t==0) s[i]=goal[SIZE-1];
        else s[i]=goal[t-1];
    }

    State start(s,s.find(goal[SIZE-1]),0);
    priority_queue<State> Q; Q.push(start);
    set<string> visited; visited.insert(s);
    while(!Q.empty()){
        auto cur=Q.top(); Q.pop();
        if(cur.str==goal){
            cout<<cur.distFromS<<endl;
            return 0;
        }
        for(int i=0;i<4;i++){
            int nxtspace=cur.space+d[i];
            if(nxtspace<0 or nxtspace>=SIZE) continue;
            if(d[i]==1 and nxtspace%W==0) continue;
            if(d[i]==-1 and nxtspace%W==W-1) continue;
            string nxtstr=cur.str;
            swap(nxtstr[cur.space],nxtstr[nxtspace]);
            if(!visited.count(nxtstr)){
                visited.insert(nxtstr);
                State nxt(nxtstr,nxtspace,cur.distFromS+1);
                Q.push(nxt);
            }
        }
    }
    return 0;
}