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 <stdio.h>
#include <stdlib.h>

#define N 4
#define NN N*N
#define LIMIT 100

int H[NN][NN];//マンハッタン距離の組み合わせの集合
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0}; //方向
int states_count = 0;

void swap(int *x,int *y){
  int tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

typedef struct puzzle
{
  int field[NN];//どの場所になんの数字が入っているか
  int space;//空マス
  int h_value;//マンハッタン距離
}Puzzle;

Puzzle state;//現在の状態
int limit;//深さの制限
int path[LIMIT];

int heuristic(Puzzle pz){
  int sum = 0;
  int i;
  for(i=0; i<NN; i++){
    if(pz.field[i] == NN)continue; //正しい位置にあればそのまま
    sum += H[i][pz.field[i] - 1];//マンハッタン距離を加える
  }
  return sum;
}

int isSolved(){
  int i;
  for (int i = 0; i < NN; ++i)if(state.field[i] != i+1)return 0;
  return 1;
}

int dfs(int depth, int prev){
  states_count++;
  if(state.h_value == 0)return 1; //終了
  if(depth + state.h_value > limit)return 0;

  int sx = state.space / N; //空のマスのx座標;
  int sy = state.space % N; //空のマスのy座標;

  Puzzle tmp;
  int r;
  for(r = 0;r < 4;r++){
    int tx = sx + dx[r]; //空のマスの次の位置
    int ty = sy + dy[r];
    if(tx < 0|| ty <0||tx >= N||ty >= N)continue; //行けないマスはスルー
    if((prev - r == 2)||(prev - r == -2))continue;//一個前の状態に戻る操作はスルー
    tmp = state;
    state.h_value -= H[tx * N + ty][state.field[tx * N + ty]-1];//入れ替わった分のマンハッタンん距離の増減を加算
    state.h_value += H[sx * N + sy][state.field[tx * N + ty]-1];
    swap(&state.field[tx * N + ty],&state.field[sx * N + sy]);
    state.space = tx * N + ty;
    if(dfs(depth+1,r) != 0){path[depth] = r; return 1;}
    state = tmp;
  }
  return 0;
}

int iterative_deepening(Puzzle in){
  in.h_value = heuristic(in);

  for(limit = in.h_value;limit <= LIMIT; limit++){//limit = c
    state = in;
    if(dfs(0,-100) != 0){
      //pathに入っている文字数を数えたい
      int count = 0,l;
      for(l=0;l<limit;l++){
        if(path[l] != ' ')count++;
      }
      return count;

    }
  }
  return -1;
}

int main(void){
  int i,j;
  for(i=0;i<NN;i++){
    for(j=0;j<NN;j++){
      H[i][j] = abs(i/N - j/N) + abs(i%N -j%N);//マンハッタン距離の組み合わせの初期化
    }
  }

  Puzzle in;//初期のパズル

  for(i=0;i<NN;i++){
    scanf("%d", &in.field[i]);
    if(in.field[i]==0){
      in.field[i] = NN;
      in.space = i;
    }
  }

  int ans = iterative_deepening(in);
  printf("%d\n",ans);
  //printf("states_count = %d\n", states_count);
  return 0;

}