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 num = 16, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 4;
const char wa[] = { 'u', 'l', 'd', 'r' };
int md[num][num];
vector<int> way;
int lm;


struct puzzle {
    int sp, p[num], mdp;
    string way;
    bool operator < (const puzzle &pu) const {
        for (int i = 0; i < num; i++) {
            if (p[i] == pu.p[i]) continue;
            return p[i] < pu.p[i];
        }
        return false;
    }
};

puzzle pu;

bool dfs(int de, int pr) {
    if (de + pu.mdp > lm) return false;
    if (pu.mdp == 0) return true;
    int sx = pu.sp / nd;
    int sy = pu.sp % nd;
    int tx, ty, ns;
    puzzle tmp;
    for (int r = 0; r < nd; r++) {
        if (max(r, pr) - min(r, pr) == 2) continue;
        tx = sx + ud[r];
        ty = sy + lr[r];
        tmp = pu;
        if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
        ns = tx * nd + ty;
        pu.mdp -= md[ns][pu.p[ns]- 1];
        pu.mdp += md[pu.sp][pu.p[ns] - 1];
        pu.sp = ns;
        swap(pu.p[ns], pu.p[sx * nd + sy]);
        if (dfs(de + 1, r)) {
            way.push_back(r);
            return true;
        }
        pu = tmp;
    }
    return false;
}

int main() {
    puzzle p;
    int sum = 0;
    for (int i = 0; i < num; i++) {
        cin >> p.p[i];
        if (!p.p[i]) { p.sp = i; p.p[i] = num; }
    }
    for (int i = 0; i < num; i++)
        for (int j = 0; j < num; j++)
            md[i][j] = abs(i / nd - j / nd) + abs(i%nd - j%nd);
    for (int i = 0; i < num; i++) {
        if (p.p[i] == num) continue;
        sum += md[i][p.p[i] - 1];
    }
    p.mdp = sum;
    pu = p;
    for (lm = p.mdp; lm < 100; lm++) {
        if (dfs(0, -5/*, pu*/)) {
            cout << way.size() << endl; return 0;
        }
    }
}