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 <cmath>
#include <string>
#include <map>
#include <queue>
using namespace std;
#define N 16

struct data{
  int f[N];
  int move;
  int m;
  int cost;

  bool operator < (const data &p) const {
    for(int i = 0;i < N;i++){
      if(f[i] == p.f[i]) continue;
      return f[i] < p.f[i];
    }
    return false;
  }
};

struct node{
  data puzzul;
  int e;
  
  bool operator < (const node &s) const {
      return e > s.e;
  }
};

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char where[4] = {'r', 'u', 'l', 'd'};
int M[N][N];

int getmd(data);
int astar(data);

int main(){
  data a;
  int i,j;
  string c; ///////

  for(i = 0;i < N;i++){
    for(j = 0;j < N;j++){
      M[i][j] = abs(i / (N/4) - j / (N/4)) + abs(i % (N/4) - j % (N/4));
    }
  }
  for(i = 0;i < N;i++){
    cin >> a.f[i];
    if(a.f[i] == 0){
      a.f[i] = N;
      a.move = i;
    }
  }
  cout << astar(a) << endl;

  return 0;
}

int getmd(data p){
  int i,sum = 0;
  
  for(i = 0;i < N;i++){
    if(p.f[i] == N) continue;
    sum += M[i][p.f[i] - 1];
  }
    return sum;
}

int astar(data p){
  priority_queue<node> PQ;
  map<data,bool> V;
  data x,y; ////////x=u,y=v
  node ini;
  node pt,ne; ////st=pt
  int px,py,tx,ty,i;/////////////////
  p.m = getmd(p);
  p.cost = 0;
  ini.puzzul = p;
  ini.e = getmd(p);
  PQ.push(ini);
  
  while(!PQ.empty()){
    pt = PQ.top(); PQ.pop();
    x = pt.puzzul;
    if(x.m == 0) return x.cost;
    V[x] = 1;
    px = x.move / (N/4);
    py = x.move % (N/4);
    for(i = 0;i < 4;i++){
      tx = px + dx[i];
      ty = py + dy[i];
      if(tx < 0 || ty < 0 || tx >= (N/4) || ty >= (N/4)) continue;
      y = x;
      y.m -= M[tx * (N/4) + ty][y.f[tx * (N/4) + ty] - 1];
      y.m += M[px * (N/4) + py][y.f[tx * (N/4) + ty] - 1];
      swap(y.f[px * (N/4) + py],y.f[tx * (N/4) + ty]);
      y.move = tx * (N/4) + ty;
      if(!V[y]){
	y.cost++;
	ne.puzzul = y;
	ne.e = y.cost + y.m;
	PQ.push(ne);
      }
    }
  }
  return -1;
}