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 <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int LIMIT = 100;
int MDT[16][16];
vector<int> puzzle(16);
int zero, val, limit;
int dfs(int depth, int prev)
{
    if(val == 0) return depth;
    if(depth + val >= limit) return LIMIT;
    int res = LIMIT;
    for(int i = 0; i < 4; i++)
    {
        if((i + 2) % 4 == prev) continue;
        int y = zero / 4, x = zero % 4;
        int ny = y + dy[i], nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= 4 || nx >= 4) continue;
        vector<int> tmp(puzzle);
        for(int j = 0; j < 16; j++) tmp[j] = puzzle[j];
        int tmp_zero = zero, tmp_val = val;
        int piece_idx = ny * 4 + nx, piece_num = puzzle[piece_idx];
        val -= MDT[zero][15];
        val -= MDT[piece_idx][piece_num];
        val += MDT[zero][piece_num];
        val += MDT[piece_idx][15];
        swap(puzzle[zero], puzzle[piece_idx]);
        zero = piece_idx;
        res = min(dfs(depth + 1, i), res);
        puzzle = tmp, zero = tmp_zero, val = tmp_val;
    }
    return res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    for(int i = 0; i < 16; i++) for(int j = 0; j < 16; j++) MDT[i][j] = abs(i / 4 - j / 4) + abs(i % 4 - j % 4);
    for(int i = 0; i < 16; i++)
    {
        cin >> puzzle[i];
        if(puzzle[i] == 0) zero = i, puzzle[i] = 15;
        else puzzle[i]--;
        val += abs(i / 4 - puzzle[i] / 4) + abs(i % 4 - puzzle[i] % 4);
    }
    int ans = INF;
    for(int i = val; i <= LIMIT; i++)
    {
        limit = i;
        ans = dfs(0, -1);
        if(ans < LIMIT)
        {
            cout << ans << endl;
            break;
        }
    }
    return 0;
}