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>
#define rep(i, n) for(int i=0;i<n;i++)
#define N 16
#define SQRTN 4
#define LIMIT 100
using namespace std;

int limit;
int searchV[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};

struct Board{
  int b[N], h;
  int calcHeust(void){
    h = 0;
    for(int i = 0; i < SQRTN; i++){
      for(int j = 0; j < SQRTN; j++){
        if(b[i*SQRTN + j] == N-1) continue;
        h += abs(b[i*SQRTN + j]/SQRTN-i) + abs(b[i*SQRTN + j]%SQRTN-j);
      }
    }
    return h;
  }
};

void printBoard(Board b){
    rep(i, SQRTN){
     rep(j, SQRTN){
       cout << b.b[i*SQRTN + j];
     }
     cout << endl;
    }
}


Board currentState;

bool dfs(int depth, int prev, int cbX, int cbY){
  currentState.calcHeust();
  if ( currentState.h == 0) return true;
  if ( depth + currentState.h > limit ) return false;
  
  for (int d = 0 ; d < 4 ; d++ ){
    int sx = cbX + searchV[d][0];
    int sy = cbY + searchV[d][1];
    if ( abs(d - prev) == 2 ) continue;
    if ( sx < 0 || sy < 0 || sx >= SQRTN || sy >= SQRTN) continue;

    swap(currentState.b[cbY*SQRTN + cbX], currentState.b[sy*SQRTN + sx]);
    if (dfs(depth+1, d, sx, sy)) return true;
    swap(currentState.b[cbY*SQRTN + cbX], currentState.b[sy*SQRTN + sx]);
  }
  
  return false;
}

int idastar(Board in, int px, int py){
  for (limit=0;limit < LIMIT;limit++){
    currentState = in;
    if (dfs(0, 100, px, py)) return limit;
  }
  return -1;
}

int main(void){
  Board init;
  int p0x, p0y;
  rep(i, N){
    cin >> init.b[i];
    if (init.b[i]==0){
      init.b[i] = N;
      p0y = i/SQRTN;
      p0x = i%SQRTN;
    }
    init.b[i]--;
  }
  cout << idastar(init, p0x, p0y) << endl;;
}