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 <cstdio>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>

using namespace std;
#define N 4
#define NN N*N

static const int dx[4] = {0,-1,0,1};
static const int dy[4] = {1,0,-1,0};
int H[NN][NN];
int state_count;

struct Puzzle
{
  int field[NN],space,MD;
  int cost;

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

struct State
{
  Puzzle puzzle;
  int f_value;
  bool operator < (const State &s) const{
    return f_value > s.f_value;
  }
};

int getTotalMD(Puzzle pz){
    int sum=0;
    for(int i=0; i<NN; i++) {
    if( pz.field[i] == NN ) continue;
    sum += H[i][pz.field[i]-1];
    }
    return sum;
}

bool isSolved(Puzzle pz){
  int i;
  for (int i = 0; i < NN; ++i)if(pz.field[i] != i+1)return false;
  return true;
}

int astar(Puzzle pz){
  priority_queue<State> q;
  pz.MD = getTotalMD(pz);
  pz.cost = 0;
  map<Puzzle,bool> V;
  Puzzle u,v;
  State initial;
  initial.puzzle = pz;
  initial.f_value= getTotalMD(pz);
  q.push(initial);

  while(!q.empty()){
    State st = q.top(); q.pop();state_count++;
    u = st.puzzle;
    if( isSolved(u) ) return u.cost;
    V[u] = true;

    int sx = u.space / N;
    int sy = u.space % N;

    for(int r=0; r<4; r++) {
        int tx = sx + dx[r];
        int ty = sy + dy[r];
        if( tx<0 || ty<0 || tx>=N || ty>=N ) continue;
        v = u;

        v.MD -= H[tx*N+ty][v.field[tx*N+ty]-1];
        v.MD += H[sx*N+sy][v.field[tx*N+ty]-1];

        swap(v.field[sx*N+sy], v.field[tx*N+ty]);
        v.space = tx*N+ty;
        if( !V[v] ) {
        v.cost++;
        State news;
        news.puzzle = v;
        news.f_value = v.cost + v.MD;
        q.push(news);
        }
    }
    }
    return -1;
}

int main(){
for(int i = 0; i<NN; i++)
  for(int j =0;j < NN;j++)
    H[i][j] = abs(i / N - j / N) + abs(i % N - j % N);

  Puzzle in;

  for(int i=0;i<NN;i++){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = NN;
      in.space = i;
    }
  }

  cout << astar(in) << endl;
  //cout <<"state_count="<<state_count<<endl;
  return 0;
}