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;
#define int long long

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

int mat[N][N];
int lim;

int getMD(){
  int sum = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(mat[i][j] == N*N-1) continue;
      sum += abs(mat[i][j]/4-i) + abs(mat[i][j]%4-j);
    }
  }
  return sum;
}

bool IDAstar(int depth,int prev,int py,int px){
  int MD = getMD();
  if(MD == 0) return true;
  if(depth + MD > lim) return false;

  for(int k = 0; k < 4; k++){
    int ny = py + dy[k];
    int nx = px + dx[k];
    if(ny < 0 || N <= ny || nx < 0 || N <= nx) continue;
    if(abs(k - prev) == 2) continue;
    swap(mat[ny][nx],mat[py][px]);
    if(IDAstar(depth+1,k,ny,nx)) return true;
    swap(mat[ny][nx],mat[py][px]);
  }
  return false;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int py,px;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> mat[i][j];
      if(mat[i][j] == 0){
        mat[i][j] = N*N;
        py = i;
        px = j;
      }
      mat[i][j]--;
    }
  }

  for(lim = 0; lim < 100; lim++){
    if(IDAstar(0,100,py,px)){
      cout << lim << endl;
      return 0;
    }
  }

  return 0;
}