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<(n);i++)

typedef long long ll;
typedef pair<int, int> P;
typedef pair< P, vector<int> > Q;

#define MAX 100005
#define INF 1001001001

int n = 4;
int sft = log2(n*n)+0.5;
vector< vector<int> > board(n, vector<int>(n));
P xpos;
int heu;
ll bstat;
int min_res, next_min_res;
map<ll,int> step;

// i,jで指定した位置のピースについて、現在位置とゴールとのマンハッタン距離
int mh(int r, int c) {
  int num = board[r][c];
  if (num == n*n-1) return 0;
  return abs(num/n - r) + abs(num%n - c); 
}

void bmove(int r, int c) {
  int xr, xc;
  tie(xr,xc) = xpos;
  ll swpbit = board[r][c] ^ board[xr][xc];
  heu -= mh(r,c);
  swap(board[xr][xc], board[r][c]);
  heu += mh(xr,xc);
  bstat ^= swpbit << ((r*n+c)*sft);
  bstat ^= swpbit << ((xr*n+xc)*sft);
  xpos = {r,c};
}

bool dfs(int g) {
  if (g+heu > min_res) {
    next_min_res = min(next_min_res, g+heu);
    return false;
  }
  if (heu == 0) return true;
  if (step.count(bstat) && step[bstat] < g) return false;
  step[bstat] = g;

  vector<int> dx = { -1,  0,  1,  0 };
  vector<int> dy = {  0, -1,  0,  1 };
  rep(i,4) {
    int r, c;
    tie(r,c) = xpos;
    int nr = r + dx[i];
    int nc = c + dy[i];
    if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
    bmove(nr,nc);
    if(dfs(g+1)) return true;
    bmove(r,c);
  }
  return false;
}

int main(int, char**)
{
  bstat = 0;
  rep(i,n)rep(j,n) {
    cin >> board[i][j];
    board[i][j]--;
    if (board[i][j] == -1) {
      xpos = {i, j};
      board[i][j] = n*n-1;
    }
    bstat |= (ll)board[i][j] << ((i*n+j)*sft);
  }
  heu = 0;
  rep(i,n)rep(j,n) {
    heu += mh(i,j);
  }
  min_res = heu;
  next_min_res = INF;
  while (!dfs(0)) {
    min_res = next_min_res;
    next_min_res = INF;
  }

  cout << min_res << endl;

  return 0;
}