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 REP(i, s, n) for (int i = s; i < n; i++)
#define rep(i, n) REP(i, 0, n)

#define LEN 4

using namespace std;

// data
int8_t P[LEN][LEN];

void solve();
int main(){
    rep(i, LEN){
        rep(j, LEN){
            int p; cin >> p;
            P[i][j] = p;
        }
    }

    solve();
}

int manhattan(int8_t (*P)[LEN])
{
    int dst = 0;
    rep(i, LEN){
        rep(j, LEN){
            if(P[i][j] == 0) continue;

            int ti = (P[i][j] - 1) / LEN,
                tj = (P[i][j] - 1) % LEN; // target location
            dst += abs(ti - i) + abs(tj - j);
        }
    }

    return dst;
}

typedef pair<int, int> Pi;

struct State{
    State(int8_t (*P0)[LEN], int move0, Pi blankBef, Pi blankNow)
    {
        rep(i, LEN)
            rep(j, LEN)
                P[i][j] = P0[i][j];
        move = move0;
        dst = manhattan(P) + move;
        blank = blankNow;
        _blank = blankBef;
    }
    friend bool operator>(State s0, State s1){
        return s0.dst > s1.dst;
    }
    int dst;
    int move;
    int8_t P[LEN][LEN];
    pair<int, int> blank, _blank;
};

const int di[4] = {-1, 1, 0 ,0},
    dj[4] = {0,0,-1, 1};
void solve(){
    // find blank
    int bi, bj;
    rep(i, LEN)
        rep(j, LEN) if (P[i][j] == 0) bi = i,
                                    bj = j;

    State s0(P, 0, Pi(bi, bj), Pi(bi, bj));
    priority_queue<State, vector<State>, greater<State> > pq;
    pq.push(s0);

    while(!pq.empty()){
        State s = pq.top(); pq.pop();

        // check final
        if(manhattan(s.P) == 0){
            cout << s.move << endl;
            break;
        }
        
        rep(i, 4){
            int ii, jj;
            ii = s.blank.first + di[i];
            jj = s.blank.second + dj[i];

            if(ii>=0&&ii<LEN && jj>=0&&jj<LEN && Pi(ii, jj)!= s._blank){
                swap(s.P[s.blank.first][s.blank.second], 
                    s.P[ii][jj]);

                pq.push(State(s.P, s.move+1, s.blank, Pi(ii, jj)));

                swap(s.P[s.blank.first][s.blank.second],
                     s.P[ii][jj]);
            }
        }
    }
}