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;

typedef unsigned long long ull;

typedef vector<char> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
typedef pair<P,mat> P1;

ull tohash(mat &A){
  
  ull res = 0;
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      res = res * 1777771 + A[i][j];
      
    }
    
  }
  
  return res;
}

bool check(mat &A){
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      int num = ( i * 4 + j + 1 ) % 16;
      
      if( A[i][j] != num ) return false;
      
    }
    
  }
  
  return true;
}

int yosou(mat &A){
  
  int res = 0;
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      if( A[i][j] ){
	
	int y = ( A[i][j] - 1 ) / 4;
	int x = ( A[i][j] - 1 ) % 4;
	
	res += abs( i - y ) + abs( j - x );
	
      }
      
    }
    
  }

  return res;
}

int dijkstra(mat s){
  
  priority_queue<P1,vector<P1>,greater<P1> > Q;
  unordered_map<ull,P> memo;
    
  memo[ tohash( s ) ] = P( yosou( s ), 0 );
  
  Q.push( P1( P( yosou( s ), 0 ), s ) );
  
  while( !Q.empty() ){
    
    P1 t = Q.top(); Q.pop();
    
    int ycost = t.first.first;
    int cost = t.first.second;
    mat A = t.second;
    
    if( check( A ) == true ) return cost;
    
    //if( ycost > memo[ tohash( A ) ].first ) continue;
    
    int y, x;
    
    for(int i=0;i<4;i++){
      
      for(int j=0;j<4;j++){
	
	if( A[i][j] == 0 ) y = i, x = j;
	
      }
      
    }
    
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
    
    for(int i=0;i<4;i++){
      
      int ny = y + dy[i], nx = x + dx[i];
      
      if( ny < 0 || nx < 0 || 4 <= ny || 4 <= nx ) continue;
      
      swap( A[y][x], A[ny][nx] );
      
      int ncost = cost + 1;
      int nycost = ncost + yosou( A );
      
      if( nycost > 45 ){
	swap( A[y][x], A[ny][nx] );
	continue;
      }
      
      ull hash = tohash( A );
      
      if( !memo.count( hash ) ){
	
	memo[ hash ] = P( nycost, ncost );
	Q.push( P1( P( nycost, ncost ), A ) );
	
      }
      
      swap( A[y][x], A[ny][nx] );
      
    }
    
  }
  
  return 0; 
}

signed main(){
  
  mat s = mat( 4, vec( 4 ) );
  
  for(int i=0;i<4;i++){
    
    for(int j=0;j<4;j++){
      
      int a;
      cin>>a;
      
      s[i][j] = (char)a;
      
    }
    
  }
  
  cout<<dijkstra(s)<<endl;
  
  return 0;
}