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 rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1001001001;
typedef unsigned long long ll;

static const int dx[4] = {1, 0, -1, 0};
static const int dy[4] = {0, 1, 0, -1};
int MDT[16][16];

struct Puzzle{
  int f[16];
  int space;
  int cnt;
  int MD;

  bool operator < (const Puzzle &p) const {
    rep(i, 16){
      if(f[i] == p.f[i]) continue;
      return f[i] < p.f[i];
    }
    return false;
  }
};

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


int getALLMD(Puzzle pz){
  int sum = 0;
  rep(i, 16){
    if(pz.f[i] == 16) continue;
    sum += MDT[i][pz.f[i]-1];
  }
  return sum;
}

int astar(Puzzle in) {
  priority_queue<State> PQ;
  in.MD = getALLMD(in);
  in.cnt = 0;
  map<Puzzle, bool> V;
  Puzzle u, v;
  State initial;
  initial.puzzle = in;
  initial.estimated = in.MD;
  V[in] = true;
  PQ.push(initial);
  int ans;
  while(!PQ.empty()){
    State st = PQ.top(); PQ.pop();
    u = st.puzzle;
    if(u.MD == 0) return u.cnt;
    int sx = u.space / 4;
    int sy = u.space % 4;
    rep(i, 4){
      int tx = sx + dx[i];
      int ty = sy + dy[i];
      if(tx<0 || ty<0 || 4<=tx || 4<=ty) continue;
      v = u;
      v.MD -= MDT[tx*4+ty][v.f[tx*4+ty]-1];
      v.MD += MDT[sx*4+sy][v.f[tx*4+ty]-1];
      swap(v.f[sx*4+sy], v.f[tx*4+ty]);
      v.space = tx * 4 + ty;
      if(!V[v]){
        v.cnt++;
        State news;
        news.puzzle = v;
        int tmp =  v.cnt + v.MD;
        news.estimated = tmp;
        if(tmp <= 45){
          V[v] = true;
          PQ.push(news);
        }
      }
    }
  }
  return -1;
}

int main(){
  rep(i, 16){
    rep(j, 16){
      MDT[i][j] = abs(i/4-j/4) + abs(i%4 - j%4);
    }
  }

  Puzzle in;
  rep(i, 16){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = 16;
      in.space = i;
    }
  }

  cout << astar(in) << endl;

  return 0;
}