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 <stack>
#include <cstdlib>
#include <vector>
#define N 4
#define N2 16
#define MAX_DEPTH 45 
using namespace std;

class game{
  public:
  int board[N2];
  int w;
  int last_move;
  int depth;
  int mnh;
};
game start;

vector<int> move_list[N2];
int dist[N2][N2];

void print(game &g){
  for(int i=0;i<N2;i++){
    printf(" %d",g.board[i]);
  }
  cout<<" mnh: "<<g.mnh<<endl;
}


bool dfs(int depth){
  stack<game> s;
  s.push(start);
  
  game g;
  while(!s.empty()){
    g=s.top();s.pop();
    if(g.mnh==0) return true;
    if(g.depth==depth) continue;
    if(g.depth+g.mnh>depth) continue;

    for(int move:move_list[g.w]){
      if(g.last_move==-move) continue;
      game h=g;
      int to=h.w+move;
      h.mnh -= dist[to][h.board[to]-1];
      h.mnh += dist[h.w][h.board[to]-1];
      swap(h.board[h.w],h.board[to]);
      h.w = to;
      h.depth++;
      h.last_move=move;
      s.push(h);
    }
  }
  return false;
}

void initialize(){
  for(int i=0;i<N2;i++){
    if(i%N<N-1) move_list[i].push_back(1);
    if(i%N>0  ) move_list[i].push_back(-1);
    if(i/N<N-1) move_list[i].push_back(N);
    if(i/N>0  ) move_list[i].push_back(-N);
  }

  //i=board,j=piece-1
  for(int i=0;i<N2;i++){
    for(int j=0;j<N2;j++){
      dist[i][j] = abs(j%N-i%N) + abs(j/N-i/N);
    }
  }

  start.mnh=0;
  for(int i=0;i<N2;i++){
    if(i==start.w) continue;
    start.mnh += dist[i][start.board[i]-1];
  }
}

int solve(){
  initialize();
  for(int i=start.mnh;i<=MAX_DEPTH;i++){
    if(dfs(i)){
      return i;
    }
  }
  return -1;
}

int main(){
  for(int i=0;i<N2;i++){
    int tmp; cin>>tmp;
    if(tmp==0){
      start.board[i]=N2;
      start.w=i;
    }else{
      start.board[i]=tmp;
    }
  }
  start.depth=0;
  start.last_move=0;

  cout<<solve()<<endl;
}