#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
/*const int num = 16, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 4;
const char wa[] = { 'u', 'l', 'd', 'r' };
int md[num][num];
vector<int> way;
int lm;
struct puzzle {
	int sp, p[num], mdp;
	string way;
	bool operator < (const puzzle &pu) const {
		for (int i = 0; i < num; i++) {
			if (p[i] == pu.p[i]) continue;
			return p[i] < pu.p[i];
		}
		return false;
	}
};
puzzle pu;
bool dfs(int de, int prev, puzzle pu) {
	if (pu.mdp + de > lm) return false;
	//cout << "mdp" << pu.mdp << endl;
	if (!pu.mdp) { return true; }
	int sx = pu.sp / nd;
	int sy = pu.sp % nd;
	int tx, ty, ns;
	puzzle tmp = pu;
	for (int r = 0; r < nd; r++) {
		if (max(r, prev) - min(r, prev) == 2) continue;
		tx = sx + ud[r];
		ty = sy + lr[r];
		if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
		ns = tx * nd + ty;
		tmp.mdp = pu.mdp - md[ns][pu.p[ns] - 1] + md[sx*nd + sy][pu.p[ns] - 1];
		tmp.sp = ns;
		swap(tmp.p[ns], tmp.p[tmp.sp]);
		if (dfs(de + 1, r, tmp)) { way.push_back(r); return true; };
	}

	return false;
}
bool dfs(int de, int prev, puzzle pu) {
	if (pu.mdp + de > lm) return false;
	//cout << "prev" << prev << "pu.sp" << pu.sp << "mdp" <<  pu.mdp << endl;
	if (!pu.mdp) { return true; }
	int sx = pu.sp / nd;
	int sy = pu.sp % nd;
	int tx, ty, ns;
	puzzle tmp = pu;
	for (int r = 0; r < nd; r++) {
		if (max(r, prev) - min(r, prev) == 2) continue;
		tx = sx + ud[r];
		ty = sy + lr[r];
		tmp = pu;
		if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
		ns = tx * nd + ty;
		tmp.mdp = pu.mdp - md[ns][pu.p[ns] - 1] + md[sx*nd + sy][pu.p[ns] - 1];
		tmp.sp = ns;
		swap(tmp.p[ns], tmp.p[sx * nd + sy]);
		if (dfs(de + 1, r, tmp)) {
			//cout << "r" << r << "sp" << pu.sp << endl;
			way.push_back(r);
			return true;
		}
	}
	return false;
}
int main() {
	int sum = 0;
	for (int i = 0; i < num; i++) {
		cin >> pu.p[i];
		if (!pu.p[i]) pu.sp = i;
	}
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			md[i][j] = abs(i / nd - j / nd) + abs(i%nd - j%nd);
	for (int i = 0; i < num; i++)
		sum += md[i][pu.p[i] - 1];
	pu.mdp = sum;
	for (lm = pu.mdp; lm < 100; lm++) {
		if (dfs(lm, -5, pu)) {
			cout << way.size() << endl; return 0;
		}
	}
}*/


const int num = 16, ud[] = { -1, 0, 1, 0 }, lr[] = { 0, -1, 0, 1 }, nd = 4;
const char wa[] = { 'u', 'l', 'd', 'r' };
int md[num][num];
vector<int> way;
int lm;
struct puzzle {
	int sp, p[num], mdp;
	string way;
	bool operator < (const puzzle &pu) const {
		for (int i = 0; i < num; i++) {
			if (p[i] == pu.p[i]) continue;
			return p[i] < pu.p[i];
		}
		return false;
	}
};
puzzle pu;
bool dfs(int de, int prev, puzzle pu) {
	if (pu.mdp + de> lm) return false;
	//cout << "prev" << prev << "pu.sp" << pu.sp << "mdp" <<  pu.mdp << endl;
	if (!pu.mdp) {return true; }
	int sx = pu.sp / nd;
	int sy = pu.sp % nd;
	int tx, ty, ns;
	puzzle tmp = pu;
	for (int r = 0; r < nd; r++) {
		if (max(r, prev) - min(r, prev) == 2) continue;
		tx = sx + ud[r];
		ty = sy + lr[r];
		tmp = pu;
		if (tx >= nd || tx < 0 || ty >= nd || ty < 0) continue;
		ns = tx * nd + ty;
		tmp.mdp = pu.mdp - md[ns][pu.p[ns]-1] + md[sx*nd + sy][pu.p[ns]-1];
		tmp.sp = ns;
		swap(tmp.p[ns], tmp.p[sx * nd + sy]);
		if (dfs(de + 1, r, tmp)) { 
			//cout << "r" << r << "sp" << pu.sp << endl;
			way.push_back(r);
			return true; 
		}
	}
	return false;
}
int main() {
	int sum = 0;
	for (int i = 0; i < num; i++) {
		cin >> pu.p[i];
		if (!pu.p[i]) { pu.sp = i; pu.p[i] = num; }
	}
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			md[i][j] = abs(i / nd - j / nd) + abs(i%nd - j%nd);
	for (int i = 0; i < num; i++) {
		if (pu.p[i] == num) continue;
		sum += md[i][pu.p[i] - 1];
	}
	pu.mdp = sum;
	for (lm = pu.mdp; lm < 100; lm++) {
		if (dfs(0, -5, pu)) {
			cout << way.size() << endl; return 0;
		}
	}
}

Measured memory_bytes: 3180