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<cmath>
using namespace std;

const int N = 4;
const int N2 = 16;
const int LIMIT = 45;
const int mx[4] = {0,-1,0,1};
const int my[4] = {-1,0,1,0};

struct Puzzle {
    int p[N2], h, d;
};

Puzzle ans;
int limit, md[N2][N2];

bool visit(Puzzle a,int prev) {
    if(a.h==0) {
        ans = a;
        return true;
    }
    if(a.d + a.h > limit) return false;
    int blank; Puzzle b;
    for(int i=0; i<N2; i++) {
        if(a.p[i]==0) blank=i;
    }
    int bx = blank%N, by = blank/N;

    for(int i=0; i<4; i++) {
        int x=bx+mx[i],y=by+my[i];
        if(x<0 || x>=N || y<0 || y>=N) continue;
        if(abs(prev-i) == 2) continue;
        b = a;
        b.h += md[blank][b.p[y*N+x]-1] - md[y*N+x][b.p[y*N+x]-1];
        swap(b.p[blank],b.p[y*N+x]);
        b.d++;
        if(visit(b,i)) return true;
    }
    return false;
}

void IDA(Puzzle init) {
    for(int i=0; i<N2; i++)
        if(init.p[i]!=0) init.h+=md[i][init.p[i]-1];
    for(limit=init.h; limit <= LIMIT; limit++) {
        if(visit(init,10)) break;
    }
}

int main() {
    Puzzle init;
    init.h = init.d = 0;
    for(int i=0; i<N2; i++)
        for(int j=0; j<N2; j++)
            md[i][j] = abs(i/N-j/N)+abs(i%N-j%N);

    for(int i=0; i<N2; i++) cin >> init.p[i];
    IDA(init);
    cout << ans.d << endl;
    return 0;
}