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>
#include <string>
#include <cassert>
using namespace std;
 
const int MAX = 4;
const int NN = 16;
const int GEN = 100;
const int xdo[4] = {0, -1, 0, 1};
const int ydo[4] = {1, 0, -1, 0};
const char hira[4] = {'r', 'u', 'l', 'd'};
int RYOMA[NN][NN];
 
struct Mond {int f[NN], sawa, Atom;};
 
Mond kaku;
int mits;
int tee[GEN];
 
int getsum(Mond pz){
    int sum = 0;
    for (int i = 0; i < NN; i++){
        if (pz.f[i] == NN) continue;
        sum += RYOMA[i][pz.f[i] - 1];
    }
    return sum;
}

bool defa(int fat, int af6){
    if (kaku.Atom == 0) return true;
    if (fat + kaku.Atom > mits) return false;
 
    int sx = kaku.sawa / MAX;
    int sy = kaku.sawa % MAX;
    Mond tmp;
 
    for (int r = 0; r < 4; r++){
        int tx = sx + xdo[r];
        int ty = sy + ydo[r];
        if (tx < 0 || ty < 0 || tx >= MAX || ty >= MAX) continue;
        if (max(af6, r) - min(af6, r) == 2) continue;
        tmp = kaku;
 
        kaku.Atom -= RYOMA[tx * MAX + ty][kaku.f[tx * MAX + ty] - 1];
        kaku.Atom += RYOMA[sx * MAX + sy][kaku.f[tx * MAX + ty] - 1];
        swap(kaku.f[tx * MAX + ty], kaku.f[sx * MAX + sy]);
        kaku.sawa = tx * MAX + ty;
        if (defa(fat + 1, r)){
            tee[fat] = r;
            return true;
        }
        kaku = tmp;
    }
    return false;
}
 
string chekit(Mond in){
    in.Atom = getsum(in);
 
    for (mits = in.Atom; mits <= GEN; mits++){
        kaku = in;
        if (defa(0, -100)){
            string ans = "";
            for (int i = 0; i < mits; i++) ans += hira[tee[i]];
            return ans;
        }
    }
    return "unsolvable";
}
 
int main(){
    for (int i = 0; i < NN; i++){
        for (int j = 0; j < NN; j++){
            RYOMA[i][j] = abs(i / MAX - j / MAX) + abs(i % MAX - j % MAX);
            Mond in;
        }
    }
    Mond in;
    for (int i = 0; i < NN; i++){
        cin >> in.f[i];
        if (in.f[i] == 0){
            in.f[i] = NN;
            in.sawa = i;
        }
    }
    string ans = chekit(in);
    cout << ans.size() << endl;
 
    return 0;
}