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 <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int field[4][4], limit, MD = 0;
bool ans = false;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int MDT[4][4][16];

struct Point {
    int x;
    int y;
};

void dfs(Point nowpos, Point prevpos, int depth) {
    if (MD == 0) {
        ans = true;
        return;
    }
    if (depth + MD > limit) {
        return;
    }

    int MD_bk = MD;
    for (int i = 0; i < 4; i++) {
        Point nextpos = nowpos;
        nextpos.x += dx[i];
        nextpos.y += dy[i];
        if (nextpos.x < 0 || nextpos.x > 3 || nextpos.y < 0 || nextpos.y > 3 || (nextpos.y == prevpos.y && nextpos.x == prevpos.x)) {
            continue;
        }
        MD = MD - MDT[nextpos.y][nextpos.x][field[nextpos.y][nextpos.x]] + MDT[nowpos.y][nowpos.x][field[nextpos.y][nextpos.x]];
        swap(field[nextpos.y][nextpos.x], field[nowpos.y][nowpos.x]);
        dfs(nextpos, nowpos, depth + 1);
        swap(field[nextpos.y][nextpos.x], field[nowpos.y][nowpos.x]);
        MD = MD_bk;
    }
}

void calc_MD() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 1; k <= 15; k++) {
                MDT[i][j][k] = abs(i - (k - 1) / 4) + abs(j - (k - 1) % 4);
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (field[i][j] != 0) {
                MD += MDT[i][j][field[i][j]];
            }
        }
    }
}

int main() {
    Point space, temp;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> field[i][j];
            if (field[i][j] == 0) {
                space.x = j;
                space.y = i;
            }
        }
    }
    calc_MD();

    temp.x = temp.y = -1;
    for (int i = 0; i <= 45; i++) {
        limit = i;
        dfs(space, temp, 0);
        if (ans == true) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}