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 <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;

typedef long long lli;

const int INF = 1 << 29;
const int H = 4;
const int W = 4;
const int N = H * W;
const int MAX_ANS = 45;

/*
  反復深化＋枝狩り（ヒューリスティック？）
  「現在の手数 + '0'以外の答えまでのマンハッタン距離の合計 <= 45」になるかどうかで枝狩り
  手元では31~32手目くらいでTLEになってしまう
 */


lli pow2[N+1];
int in_pos,sumcnt;//dfscnt;
bool ans;
vector<char> inG,G,ansG;

void make(){
  pow2[0] = 1;
  for(lli i=1;i<=N;i++) {
    pow2[i] = pow2[i-1] * i;
  }
  
  for(int i=1;i<N;i++) ansG.push_back(i);
  ansG.push_back(0);
}

int nextpos(int pos, int d){
  switch(d){
    //up
  case 0:
    return pos - W;

    //right
  case 1:
    if(pos % W == W-1) return -1;
    else return pos + 1;

    //down
  case 2:
    if(pos + W >= N) return -1;
    else return pos + W;

    //left
  case 3:
    if(pos % W == 0) return -1;
    else return pos - 1;
    
  default: 
    return -1;
  }
}

int distance(int i, int j, int now){
  return abs(i - (now-1)/W) + abs(j - (now-1)%W);
}

// ansGまでのマンハッタン距離の合計
int inith(){
 int res = 0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      int now = G[i*W+j];
      if(now != 0){
        res += distance(i,j,now);
      }
    }
  }
  return res;
}

int cnt,nh;

void dfs(int pos, int prev, int h){
  int npos;
  //dfscnt++;
  if(ans) return;
  if(G == ansG){
    ans = true;
    return;
  }
  if(cnt + h > sumcnt) return;

  for(int i=0;i<4;i++){
    npos = nextpos(pos, i);
    if(npos < 0 || npos == prev) continue;
    nh = h - distance(npos/W, npos%W, G[npos]) + distance(pos/W, pos%W, G[npos]);
    if(cnt + 1 + nh <= sumcnt){
      swap(G[pos], G[npos]);
      cnt += 1;
      dfs(npos, pos, nh);
      cnt -= 1;
      swap(G[pos], G[npos]);
    }
  }
}

void solve(){
  ans = false;
  G = inG;

  for(int i=0;i<=MAX_ANS;i++){
    //cout << i << ":" << endl;
    sumcnt = i;
    //dfscnt = 0;
    cnt = 0;
    dfs(in_pos, -1, inith());
    //cout << "dfs cnt = " << dfscnt << endl;
    if(ans) {
      cout << i << endl;
      return;
    }
  }

  assert(false);
}

int main(){
  set<int> st1;
  int x;
  make();

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      assert(cin >> x);
      assert(x >= 0 && x < N);
      assert(st1.empty() || st1.find(x) == st1.end());
      st1.insert(x);
      inG.push_back(x);
      if(x == 0) in_pos = i * W + j;
    }
  }
  solve();
  
  assert(!(cin >> x));
}