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;

void debug() { cerr << "\n"; }
template <class T> void debug(const T &x) { cerr << x << "\n"; }
template <class T, class... Args> void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
template <class T> void debugVector(const vector<T> &v) {
    for(const T &x : v) {
        cerr << x << " ";
    }
    cerr << "\n";
}

//----------------------------------------------

const int N = 4;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct State {
    int a[N * N];
    int sid;
};

State now;
int ans = 45;

int h() {
    int res = 0;
    for(int i = 0; i < N * N; i++) {
        if(now.a[i] != N * N - 1) {
            res += abs(i / N - now.a[i] / N) + abs(i % N - now.a[i] % N);
        }
    }
    return res;
}

// d:今の深さ
// pre:1手前の空きマスの位置
void dfs(int d, int pre) {
    if(d + h() > ans) {
        return;
    }
    if(h() == 0) {
        ans = min(ans, d);
        return;
    }
    for(int i = 0; i < 4; i++) {
        if((now.sid / N + dy[i]) < 0 || (now.sid / N + dy[i]) >= N) {
            continue;
        }
        if((now.sid % N + dx[i]) < 0 || (now.sid % N + dx[i]) >= N) {
            continue;
        }
        int nxt_sid = (now.sid / N + dy[i]) * N + (now.sid % N + dx[i]);
        if(nxt_sid == pre) {
            continue;
        }
        int tmp = now.sid;
        swap(now.a[now.sid], now.a[nxt_sid]);
        now.sid = nxt_sid;
        dfs(d + 1, tmp);
        swap(now.a[nxt_sid], now.a[tmp]);
        now.sid = tmp;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for(int i = 0; i < N * N; i++) {
        cin >> now.a[i];
        if(now.a[i] == 0) {
            now.a[i] = N * N - 1;
            now.sid = i;
        } else {
            now.a[i]--;
        }
    }
    dfs(0, -1);
    cout << ans << endl;
}