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 <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int x[4] = { -1,0,1,0 };
int y[4] = { 0,1,0,-1 };
int g[4][4];
int m = 0;

int h1() {
    int c = 0;
    for (int i=0;i<4;i++) {
        for (int j=0;j<4;j++) {
            if (g[i][j] != 0) {
                int t = g[i][j]-1;
                c += abs(t / 4 - i) + abs(t % 4 - j);
            }
        }
    }
    return c;
}

bool solve(int depth, int t, int zx, int zy) {
    int c = h1();
    if (c+depth>m) return false;
    if (c==0) return true;
    int dx,dy;
    for(int i=0;i<4;i++) {
        if (i != (t^2)) {
            dx = zx+x[i];
            dy = zy+y[i];
            if (dx < 0 || dx == 4 || dy < 0 || dy == 4) continue;
            swap(g[dx][dy], g[zx][zy]);
            if (solve(depth + 1, i, dx, dy)) return true;
            swap(g[dx][dy], g[zx][zy]);

        }
    }
    return false;
}

int main() {
    int zx,zy;
    for (int i=0;i<4;i++) {
        for (int j=0;j<4;j++) {
            cin>>g[i][j];
            if (g[i][j]==0) {
                zx=i;zy=j;
            }
        }
    }
    for (m=h1();;m+=2) {
        if (solve(0,9,zx,zy)) {
            cout<<m<<endl;
            return 0;
        }
    }


    return 0;
}