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>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9+5)
#define INFLL ((LL)4e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
#define SIZE 4
using namespace std;

class board{
public:
	vector<vector<int>> data;
	int ncost;
	int hcost;
	PII zpoint;

	int culonecost(int i, int j){
		if(data[i][j]==0){
			return abs(SIZE-1-i) + abs(SIZE-1-j);
		}
		int x = (data[i][j]-1)%SIZE;
		int y = (data[i][j]-1)/SIZE;
		return abs(i-y) + abs(j-x);
	}

	void setup(){
		hcost = 0;
		REP(i, SIZE){
			REP(j, SIZE){
				hcost+=culonecost(i, j);
				if(data[i][j]==0){
					zpoint=PII(i, j);
				}
			}
		}
	}

	board(vector<vector<int>> d){
		REP(i, SIZE){
			REP(j, SIZE){
				data[i][j]=d[i][j];
			}
		}
		hcost = 0;
		setup();
	}

	board(){
		data.resize(SIZE, vector<int>(SIZE));
	}

	void swap(int i, int j, int k, int l){
		hcost -= culonecost(i, j);
		hcost -= culonecost(k, l);
		std::swap(data[i][j], data[k][l]);
		hcost += culonecost(i, j);
		hcost += culonecost(k, l);
		if(data[i][j]==0){
			zpoint=PII(i, j);
		}else{
			zpoint=PII(k, l);
		}
	}

	bool onboard(int i, int j){
		return 0<=i&&0<=j&&i<SIZE&&j<SIZE;
	}
	
};

int mx[]={1, 0, -1, 0}, my[]={0, 1, 0, -1};

bool func(board &boa, int time, int lx, int ly){
	if(boa.hcost - boa.culonecost(boa.zpoint.first, boa.zpoint.second) > time * 1)return false;
	if(boa.hcost==0)return true;
	bool res = false;
	REP(i, 4){
		int y = boa.zpoint.first;
		int x = boa.zpoint.second;
		int ny = y + my[i];
		int nx = x + mx[i];
		if(lx==nx&&ly==ny)continue;
		if(!boa.onboard(ny, nx))continue;
		boa.swap(y, x, ny, nx);
		res |= func(boa, time-1, x, y);
		boa.swap(y, x, ny, nx);
		if(res)return true;
	}
	return res;
}


int main(){
	board boa;
	REP(i, SIZE)
		REP(j, SIZE)cin>>boa.data[i][j];
	boa.setup();
	REP(i, 1000){
		if(func(boa, i, -1, -1)){
			cout << i << endl;
			break;
		}
	}
	return 0;
}