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 <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <unistd.h>
#include <set>
#include <stack>
using namespace std;
#define N 4
#define N2 16
#define LIMIT 100

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

int MDT[N2][N2], ans;

class puzzle{
public:
  int f[N2], space, MD;
  void print(){
    for(int i = 0; i < N2; i++){
      cout << f[i] << " ";
      if((i + 1) % N == 0) cout << endl;
    }
  }
};

puzzle c;
int limit;

bool istarget(puzzle p){
  for(int i = 0; i < N2; i++){
    if(p.f[i] != i + 1) return false;
  }
  return true;
}

int getcost(puzzle p){
  int cost = 0;
  for(int i = 0; i < N2; i++){
    if(p.f[i] == N2) continue;
    cost += MDT[i][p.f[i] - 1];
  }
  return cost;
}

bool dfs(int d, int p){
  if(c.MD == 0){
    ans = d;
    return true;
  }
  /*if(istarget(c) == true){
    cout << c.MD << endl;
    cout << getcost(c) << endl;
    ans = d;
    return true;
  }*/
  if(d + c.MD > limit) return false;
  int x = c.space / N, y = c.space % N;
  for(int i = 0; i < 4; i++){
    puzzle n = c;
    int nx = x + dx[i], ny = y + dy[i];
    if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
    if(max(i, p) - min(i, p) == 2) continue;
    //cout << p << " " << nx * N + ny << endl;
    //if(nx * N + ny == p) continue;
    c.MD -= MDT[nx * N + ny][c.f[nx * N + ny] - 1];
    c.MD += MDT[x * N + y][c.f[nx * N + ny] - 1];
    c.space = nx * N + ny;
    //cout << d << " " << c.MD << endl;
    //cout << "(" << x << "," << y << ") -> (" << nx << "," << ny << ")\n";
    swap(c.f[x * N + y], c.f[nx * N + ny]);
    //c.print();
    if(dfs(d + 1, /*x * N + y,*/ i)) return true;
    c = n;
  }
  return false;
}

void solve(){
  for(int i = 0; i < N2; i++){
    for(int j = 0; j < N2; j++){
      int li = i / N, ci = i % N, lj = j / N, cj = j % N;
      MDT[i][j] = abs(li - lj) + abs(ci - cj);
    }
  }
  puzzle in;
  for(int i = 0; i < N2; i++){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }
  in.MD = getcost(in);
  for(limit = in.MD; limit <= LIMIT; limit++){
    c = in;
    if(dfs(0, -100)){
      cout << ans << endl;
      return;
    }
  }
  return;
}
int main(){
  solve();
  return 0;
}