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 rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
typedef uint64_t ul;
struct chtime{  
	chrono::system_clock::time_point ctm;
	chtime() { rstt();}
	void rstt() { ctm=chrono::system_clock::now();}
	uint64_t gtm(){
		auto ptm = chrono::system_clock::now() - ctm;
		return chrono::duration_cast<chrono::milliseconds>(ptm).count();
	}
	void disp(){ cerr << gtm() <<"\n";}
};
const vector<VI> cnsw ={
	{1,4},   {0,2,5},  {1,3,6}, {2,7},
	{0,5,8}, {1,4,6,9},{2,5,7,10},{3,6,11},
	{4,9,12},{5,8,10,13}, {6,9,11,14}, {7,10,15},
	{8,13},  {9,12,14}, {10,13,15}, {11,14}
};

VI bb(16);
int lv;
int mhcl(const VI& v){
	int rt=0;
	rep(i,16) if(v[i]!=0){
		int cr=v[i]-1;
		rt += abs((i>>2) - (cr>>2)) + abs((i&3) - (cr&3));
	}
	return rt;
}

bool fck(int dpt, int pr, int zr){

	int mh = mhcl(bb);
	if(mh ==0 ) return true;
	if(mh + dpt > lv) return false;
	for(int z: cnsw[zr]){
		if(z == pr) continue;
		swap(bb[z], bb[zr]);
		if(fck(dpt+1, zr, z)) return true;
		swap(bb[z], bb[zr]);
	}
	return false;
}

int main()
{

	rep(i, 16) cin >>bb[i];
	int zr;
	rep(i,16) if(bb[i]==0) zr=i;
	//chtime tm;
	for(lv=0; lv<50  ;lv++){
		if(fck(0, 999, zr)){
			cout << lv <<"\n"; break;
			//dbg(lv, tm.gtm());
		}
	}
	//tm.disp();
	return 0;
}