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 <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
#define N 4
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int MDT[N*N][N*N];
struct Puzzle {
  vector<int> f;
  int space;
  int cost;
  int MD;
  int estimated;
  bool operator < (const Puzzle &s) const {
    return estimated > s.estimated;
  }
};
int getAllMD(Puzzle pz){
  int sum = 0;
  for(int i = 0; i < N * N; i++) {
    if(pz.f[i]==0) continue;
    sum += MDT[i][pz.f[i]-1];
  }
  return sum;
}
map<vector<int>, bool> checked;
priority_queue<Puzzle> que;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  // A* -> estimated = cost(これまでのコスト) + MD(今の状態と最終状態の差(ここではマンハッタン距離の総和))
  // マンハッタン距離計算
  for(int i = 0; i < N * N; i++) {
    for(int j = 0; j < N * N; j++) {
      MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
    }
  }
  Puzzle start;
  start.f.resize(N*N);
  FOR(i,0,N*N){
    cin >> start.f[i];
    if(start.f[i] == 0) {
      start.space = i;
    }
  }
  start.cost = 0;
  start.MD = getAllMD(start);
  start.estimated = start.cost + start.MD;
  que.push(start);
  checked[start.f] = true;

  while(!que.empty()){
    Puzzle now = que.top();
    que.pop();
    if(now.MD == 0) {
      cout << now.cost << endl;
      return 0;
    }
    checked[now.f] = true;
    int x = now.space % N;
    int y = now.space / N;
    FOR(i,0,4){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
      Puzzle next = now;
      next.space = ny * N + nx;
      next.cost++;
      next.MD -= MDT[ny * N + nx][next.f[ny * N + nx]-1]; // 空白になったので
      next.MD += MDT[y * N + x][next.f[ny * N + nx]-1];
      swap(next.f[ny * N + nx], next.f[y * N + x]);
      next.estimated = next.cost + next.MD;
      if(!checked[next.f] && next.estimated <= 45){
        que.push(next);
      }
    }
  }
  return 0;
}