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<cstdlib>
#define N 16
using namespace std;
int cost = 45,pos0;
int puzzle[N];
int dis() {
  int sum = 0;
  for (int i = 0; i < N; ++i)
    if (puzzle[i] != N-1) sum += abs(i / 4 - puzzle[i] / 4) + abs(i % 4 - puzzle[i] % 4);
  return sum;
}
void fswap(int x,int y) {
  int tmp;
  tmp = puzzle[x];
  puzzle[x] = puzzle[y];
  puzzle[y] = tmp;
}
void rec(int p,int move) {
  int d = dis(); //0ならばパズル完成
  if (d + move > cost) return;
  if (d == 0) {
    cost = move;
    return;
  }
  if (p != 1 && pos0 >= 4) fswap(pos0, pos0 - 4),pos0-=4, rec(0, move + 1),pos0+=4, fswap(pos0, pos0 - 4); //上に動かせるor動かす必要がある
  if (p != 0 && pos0 < 12) fswap(pos0, pos0 + 4),pos0+=4, rec(1, move + 1),pos0-=4, fswap(pos0, pos0 + 4); //下に動かせるor動かす必要がある
  if (p != 3 && pos0 % 4 > 0) fswap(pos0, pos0 - 1),--pos0, rec(2, move + 1),++pos0, fswap(pos0, pos0 - 1); //左に動かせるor動かす必要がある
  if (p != 2 && pos0 % 4 < 3) fswap(pos0, pos0 + 1),++pos0, rec(3, move + 1),--pos0, fswap(pos0 , pos0 + 1); //右に動かせるor動かす必要がある
	
}
int main() {
  for (int i = 0; i < N; ++i) {
    cin >> puzzle[i];
    if (puzzle[i] == 0) {
      puzzle[i] = N - 1;
      pos0 = i;
    }
    else --puzzle[i];
  }
  rec(-1,0);
  cout << cost << endl;
  return 0;
}