#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

typedef pair<int, int> pii;

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int MDT[16][16];

struct State
{
	int puzzle[16];
	int depth;
	int evaluation;
	int prev;

	bool operator<(const State& s)const
	{
		return evaluation < s.evaluation;
	}

	bool operator>(const State& s)const
	{
		return evaluation > s.evaluation;
	}

	bool operator==(const State& s)const
	{
		for (int i = 0; i < 16; i++)
		{
			if (puzzle[i] != s.puzzle[i])
			{
				return false;
			}
		}
		return true;
	}
};

struct OwnNode
{
	int key[16];
	OwnNode* left;
	OwnNode* right;

	OwnNode():left(nullptr),right(nullptr){}
	OwnNode(int key[]) :OwnNode()
	{
		for (int i = 0; i < 16; i++)
		{
			this->key[i] = key[i];
		}
	}

	void insert(int nkey[])
	{
		int i = 0;
		for (; i < 16; i++)
		{
			if (key[i] != nkey[i])
			{
				break;
			}
		}
		if (i == 16)
		{
			return;
		}
		if (key[i]>nkey[i])
		{
			if (left == nullptr)
			{
				left = new OwnNode(nkey);
			}
			else
			{
				left->insert(nkey);
			}
		}
		else
		{
			if (right == nullptr)
			{
				right = new OwnNode(nkey);
			}
			else
			{
				right->insert(nkey);
			}
		}
	}

	bool find(int fkey[])
	{
		int i = 0;
		for (; i < 16; i++)
		{
			if (key[i] != fkey[i])
			{
				break;
			}
		}
		if (i == 16)
		{
			return true;
		}
		if (key[i]>fkey[i])
		{
			if (left == nullptr)
			{
				return false;
			}
			else
			{
				return left->find(fkey);
			}
		}
		else
		{
			if (right == nullptr)
			{
				return false;
			}
			else
			{
				return right->find(fkey);
			}
		}
	}

	void deleteAll()
	{
		if (left != nullptr)
		{
			left->deleteAll();
		}
		else
		{
			delete left;
			left = nullptr;
		}
		if (right != nullptr)
		{
			right->deleteAll();
		}
		else
		{
			delete right;
			right = nullptr;
		}
	}
};

State goal;

int heuristic(State& s)
{
	int sum = 0;
	for (int i = 0; i < 16;i++)
	{
		if (s.puzzle[i] == 0) continue;
		sum += MDT[i][s.puzzle[i] - 1];
	}
	return sum;
}

int solve(State start, int limit)
{
	State ts = start;

	if (ts == goal)
	{
		return ts.depth;
	}

	int zeroi = -1;
	for (int i = 0; i < 16; i++)
	{
		if (ts.puzzle[i] == 0)
		{
			zeroi = i;
			break;
		}
	}

	priority_queue<State, vector<State>, greater<State>> pq;
	for (int i = 0; i < 4; i++)
	{
		State tts = ts;

		int x = zeroi % 4 + dx[i];
		int y = zeroi / 4 + dy[i];
		int nzeroi = y * 4 + x;

		if (abs(i - tts.prev) == 2)
		{
			continue;
		}
		if (0 <= x&&x <= 3 && 0 <= y&&y <= 3)
		{
			int t = tts.puzzle[zeroi];
			tts.puzzle[zeroi] = tts.puzzle[nzeroi];
			tts.puzzle[nzeroi] = t;
			tts.depth++;
			tts.prev = i;
			tts.evaluation = heuristic(tts) + tts.depth;
			if (tts.evaluation <= limit)
			{
				pq.push(tts);
			}
		}
	}

	while (!pq.empty())
	{
		int result = solve(pq.top(), limit);
		if (result != -1)
		{
			return result;
		}
		pq.pop();
	}
	
	return -1;
}

int main()
{
	for (int i = 0; i < 16; i++)for (int j = 0; j < 16; j++)
		MDT[i][j] = abs(i / 4 - j / 4) + abs(i % 4 - j % 4);

	State start;

	goal.depth = 0;
	goal.evaluation = 0;
	goal.prev = 0;
	for (int i = 0; i < 16; i++)
	{
		goal.puzzle[i] = (i + 1) % 16;
	}

	for (int i = 0; i < 16; i++)
	{
		int n;
		cin >> n;

		start.puzzle[i] = n;
	}

	start.depth = 0;
	start.evaluation = 0;
	start.prev = -100;

	for (int i = heuristic(start); i <= 100; i += 2)
	{
		int result = solve(start, i);
		if (result != -1)
		{
			printf("%d\n", result);
			break;
		}
	}
	
	return 0;
}


Measured memory_bytes: 3264