#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include<vector>
#include<cstring>
#include<set>
#include <cstdio>
#include<queue>
#include<map>
#define WHITE 0
#define GRAY  1
#define BLACK 2
#define endl '\n'
#define forup(i,a,n) for( int i =a; i < n; i++)
#define llforup(i,a,n) for( ll i =a; i < n; i++)
#define fordown(i,a,n) for( int i =a; i >= n; i--)
#define fornot(i,a,n) for( int i=a;!n;i++)
#define mod  (ll)(1e9+7)
#define ifempty(a)  if(!a)
using namespace std;
typedef long long ll;
inline int readnum()
{
	int p, data = 0; char ch = 0;
	while ((ch != ' - ') && ch < '0' || ch>'9') ch = getchar();//相当于正则表达式的搜索，跳过不需要的字符
	if (ch == '- ')p = -1, ch = getchar();
	else p = 1;
	while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();//搜索需要的字符
	return data * p;
}
inline int ReadPossitive()
{
	char ch; int data = 0;
	ch = getchar();
	while (ch == ' ' || ch == '\n')ch = getchar();
	while (ch != ' ' && ch != '\n' && ch != EOF)
	{
		data = data * 10 + ch - '0';
		ch = getchar();
	}
	return data;
}
//E-mail 374656045@qq.com
struct Block { int dx; int dy; int MDdistance; };
class solve {
private:
	//采用双索引
	Block IndexCode[17];
	int IndexBoard[5][5];
    const Block block[17] = { {-1,-1,-1},
	{1,1,0},{1,2,0},{1,3,0}, {1,4,0},
	{2,1,0},{2,2,0},{2,3,0}, {2,4,0},
	{3,1,0},{3,2,0},{3,3,0}, {3,4,0},
	{4,1,0},{4,2,0},{4,3,0}, {4,4,0},
	};
	const char Move[4] = { 'u','d','l','r' };
	const char OppsiteMove[4] = { 'd','u','r','l' };
	//int pile;//层数,用层数不能保证求出最短路径，想想为什么
	int tempdepth; int ans;  
	int MDnext;
public:
	solve()
	{
		initial();
		int originMD = getMD();
	
		if (originMD == 0)cout << 0 << endl;
		else//经过试验，这个搜索树很均衡,bound++即可
		{
			int bound = originMD;
			while (!(ans = IDAstar(1, bound, -1)))
			{
				bound++;
			}
			cout <<ans<< endl;
		}
	}
	void initial()
	{
		int  temp;
		forup(i, 1, 4 + 1)
			forup(j, 1, 4 + 1)
		{
			temp = ReadPossitive();
			if (temp == 0)temp = 16;//预处理
			IndexBoard[i][j] = temp;
			IndexCode[temp].dx = i, IndexCode[temp].dy = j;
			IndexCode[temp].MDdistance = abs(block[temp].dx - i) + abs(block[temp].dy - j);
		}
	}
	inline int getMD()
	{
		int MDall=0;
		forup(i, 1, 16 )
			MDall += IndexCode[i].MDdistance;//MDdistance记得更新,空格的曼哈顿距离不用算
		return MDall;
	}
	int IDAstar(int depth,int bound,char premove)
	{
		//继续寻路，移动方块,把方块朝着空格移动转换为空格朝着滑块移动.
#ifdef DEBUG
		debug(depth, bound, premove);
#endif
		forup(i, 0, 4)
		{
			if (OppsiteMove[i] == premove)continue;//简单判重，其他的n步后与原来出现的情况重复的通过bound来遏制	
			if(!move(i))continue;
			MDnext = getMD();
#ifdef DEBUG
			debug('m');
#endif
			if (MDnext == -1)continue;//无法移动
			if (MDnext == 0)return depth;//完成任务
			else
			{
				if (MDnext + depth+1 <= bound)//细节多
				{
					tempdepth = IDAstar(depth + 1, bound, Move[i]);
					if (tempdepth)return tempdepth;//因为是depth++
				}
			}
			moveback(i);
#ifdef DEBUG
			debug('b');
#endif
		}
		 return 0;
	}
	bool move(int i)
	{
		int tempX, tempY, temp;
		switch (i)
		{
		case 0:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			if (tempX - 1 < 1)return false;//越界
			//更新索引1
			temp = IndexBoard[tempX - 1][tempY];
			IndexBoard[tempX-1][tempY] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;
			//更新索引2
			IndexCode[temp].dx += 1;
			IndexCode[16].dx -= 1;
			break;
		case 1:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			if (tempX + 1 > 4)return false;//越界
			temp = IndexBoard[tempX + 1][tempY];
			IndexBoard[tempX+1][tempY] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;
			IndexCode[temp].dx -= 1;
			IndexCode[16].dx += 1;
			break;
		case 2:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			if (tempY - 1 < 1)return false;//越界
			temp = IndexBoard[tempX][tempY - 1];
			IndexBoard[tempX][tempY - 1] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;
			IndexCode[temp].dy += 1;
			IndexCode[16].dy -= 1;
			break;
			
		case 3:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			if (tempY + 1 > 4)return false;//越界
			temp = IndexBoard[tempX][tempY + 1];
			IndexBoard[tempX][tempY + 1] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;
			IndexCode[temp].dy -= 1;
			IndexCode[16].dy += 1;
			break;
		}
		IndexCode[temp].MDdistance = abs(IndexCode[temp].dx - block[temp].dx) + abs(IndexCode[temp].dy - block[temp].dy);
		
		return true;
	}
	void moveback(int i)
	{
		int tempX, tempY, temp;
		switch (i)
		{
		case 0:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			temp = IndexBoard[tempX + 1][tempY];
			IndexBoard[tempX + 1][tempY] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;

			IndexCode[temp].dx -= 1;
			IndexCode[16].dx += 1;
			break;
		case 1:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			temp = IndexBoard[tempX - 1][tempY];
			IndexBoard[tempX - 1][tempY] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;

			IndexCode[temp].dx += 1;
			IndexCode[16].dx -= 1;
			break;
		case 2:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;

			temp = IndexBoard[tempX][tempY + 1];
			IndexBoard[tempX][tempY + 1] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;

			IndexCode[temp].dy -= 1;
			IndexCode[16].dy += 1;
			break;
			
		case 3:
			tempX = IndexCode[16].dx;
			tempY = IndexCode[16].dy;
			temp = IndexBoard[tempX][tempY - 1];
			IndexBoard[tempX][tempY - 1] = IndexBoard[tempX][tempY];
			IndexBoard[tempX][tempY] = temp;

			IndexCode[temp].dy += 1;
			IndexCode[16].dy -= 1;
			break;
		}
		IndexCode[temp].MDdistance = abs(IndexCode[temp].dx - block[temp].dx) + abs(IndexCode[temp].dy - block[temp].dy);
		
	}
#ifdef DEBUG
	void debug(char control)
	{
		if (control == 'm')
		{
			cout << "---------------move!!!!!!!!--------------------" << endl;
			cout << "MDnext:" << MDnext << endl;
			forup(i, 1, 4 + 1)
			{
				forup(j, 1, 4 + 1)
				{
					if (IndexBoard[i][j] == 16)printf("%2d ", 0);
					else printf("%2d ", IndexBoard[i][j]);
				}
				cout << endl;
			}
			cout << "----------------------------------------------" << endl;
		}
		if (control == 'b')
		{
			cout << "--------------------back way!!!move back!!!!------------------" << endl;
			forup(i, 1, 4 + 1)
			{
				forup(j, 1, 4 + 1)
				{
					if (IndexBoard[i][j] == 16)printf("%2d ", 0);
					else printf("%2d ", IndexBoard[i][j]);
				}
				cout << endl;
			}
			cout << "----------------------------------------------" << endl;
		}
		
	}
	void debug(int depth, int bound, char premove)
	{
		
			cout << "--------------------initial------------------" << endl;
			cout << "MDnext:" << MDnext << " depth:" << depth << " bound:" << bound  << " premove:" << premove << endl;
				forup(i, 1, 4 + 1)
			{
				forup(j, 1, 4 + 1)
				{
					if (IndexBoard[i][j] == 16)printf("%2d ", 0);
					else printf("%2d ", IndexBoard[i][j]);
				}
				cout << endl;
			}
			cout << "----------------------------------------------" << endl;
		
	}
#endif
};
int main(void)
{
	ios_base::sync_with_stdio(0); cin.tie(0);//慎用，cin和scanf混用会导致非MSC++WA
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve solution;
#ifdef DEBUG
	fclose(stdin);//关闭文件 
	fclose(stdout);//关闭文件 
#endif
	return 0;

}




Measured memory_bytes: 3192