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 <queue>
#include <set>
#include <tuple>
#include <array>

using namespace std;

const int dx[4] = {-4, -1, 1, 4};

typedef array<int,16> T;

struct Puzzle {
  T t;
  Puzzle () {
    for(int i = 0; i < 16; i++) t[i] = (i + 1) % 16;
  }
  Puzzle (T s) : t(s) {}
  bool move(int d) {
    int x = 0;
    for(int i = 0; i < 16; i++) if (t[i] == 0) x = i;
    if (d == 2 && x % 4 == 3) return false;
    if (d == 1 && x % 4 == 0) return false;
    int nx = x + dx[d];
    if (nx < 0 || nx > 15) return false;
    swap(t[x], t[nx]); x = nx;
    return true;
  }
  int eval() {
    int sum = 0;
    for(int i = 0; i < 4; i++){
      for(int j = 0; j < 4; j++){
       if (t[i*4+j] == 0) continue;
       int y = (t[i*4+j] + 15) % 16 / 4;
       int x = (t[i*4+j] + 3) % 4;
       sum += abs(i - y) + abs(j - x);
      }
    }
  return sum;
  }
  bool operator==(const Puzzle &r) { return t == r.t; }
  bool operator<(const Puzzle &r) const { return t < r.t; }
};

set<Puzzle> s;

int solve() {
  T field;
  for(int i = 0; i < 16; i++) cin >> field[i];
  Puzzle check;
  Puzzle puz(field);
  priority_queue<tuple<int,int,Puzzle>> que;
  if (puz == check) return 0;
  que.push(make_tuple(-puz.eval(), 0, puz));
  while (!que.empty()) {
    int num = get<1>(que.top());
    Puzzle b = get<2>(que.top());
    que.pop();
    for(int i = 0; i < 4; i++) {
      Puzzle nb = b;
      bool flag = nb.move(i);
      if (flag == true && s.find(nb) == s.end()) {
        if (nb == check) return num + 1;
        int ev = -nb.eval();
        s.insert(nb);
        que.push(make_tuple(ev - num - 1, num + 1, nb));
      }
    }
  }
  return -1;
}

signed main() {
  cout << solve() << endl;
}