#include <iostream>
#include <queue>
#include <cmath>
#include <utility>
#include <map>

using namespace std;

const short grid_size = 4;
const short inf = 1000;

class state_t {
public:
	short data[grid_size][grid_size];
	short heuristic_val;
	short cost;
	short zero_pos;
	pair<short, short> prev_move;
	state_t(): cost(inf), heuristic_val(inf) {}
	state_t(const short data[][grid_size]): heuristic_val(inf), cost(inf) {
		for (auto x = 0; x < grid_size; ++x) {
			for (auto y = 0; y < grid_size; ++y) {
				this->data[x][y] = data[x][y];
				if (this->data[x][y] == 0) {
					zero_pos = x * grid_size + y;
				}
			}
		}

	}

	void display() const {
		cout << zero_pos / grid_size << " " << zero_pos % grid_size << endl;
		cout << cost << " " << heuristic_val << endl;
		for (auto x = 0; x < grid_size; ++x) {
			for (auto y = 0; y < grid_size; ++y) {
				cout << data[x][y] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
	void update_heuristic() {
		short dist = 0;
		for (auto x = 0; x < grid_size; ++x) {
			for (auto y = 0; y < grid_size; ++y) {
				short val = data[x][y];
				if (val != 0) {
					short target_x = (val - 1) / grid_size;
					short target_y = (val - 1) % grid_size;
					short dx = x - target_x;
					short dy = y - target_y;
					dist += abs(dx) + abs(dy);
				}
			}
		}
		heuristic_val = dist;
	}
};



class compare_priority {
public:
	bool operator()(const state_t &u, const state_t &v) {
		return u.heuristic_val + u.cost > v.heuristic_val + v.cost;
	}

	bool operator()(const state_t &u, const state_t &v) const {
		return u.heuristic_val + u.cost > v.heuristic_val + v.cost;
	}
};

class compare_lexical {
public:
	bool operator()(const state_t &u, const state_t &v) {
		for (auto i = 0; i < grid_size; ++i) {
			for (auto j = 0; j < grid_size; ++j) {
				if (u.data[i][j] < v.data[i][j]) return true;
			}
		}
		return false;
	}

	bool operator()(const state_t &u, const state_t &v) const {
		for (auto i = 0; i < grid_size; ++i) {
			for (auto j = 0; j < grid_size; ++j) {
				if (u.data[i][j] < v.data[i][j]) return true;
			}
		}
		return false;
	}
};

void generate_state(priority_queue<state_t, vector<state_t>, compare_priority> &q, const state_t &current_state, const pair<short, short> &next_move) {
	if (current_state.prev_move.first == -next_move.first && current_state.prev_move.second == -next_move.second) return;
	short x = current_state.zero_pos / grid_size;
	short y = current_state.zero_pos % grid_size;
	short next_x = x + next_move.first;
	short next_y = y + next_move.second;
	if (next_x < 0 || next_x >= grid_size) return;
	if (next_y < 0 || next_y >= grid_size) return;

	state_t next_state(current_state.data);
	swap(next_state.data[x][y], next_state.data[next_x][next_y]);
	next_state.prev_move = next_move;
	next_state.zero_pos = next_x * grid_size + next_y;

	short next_state_cost = current_state.cost + 1;
	if (next_state_cost < next_state.cost) {
		next_state.cost = next_state_cost;
		next_state.update_heuristic();
		q.push(next_state);
	}
}

void bfs(state_t initial_state, state_t target) {
	priority_queue<state_t, vector<state_t>, compare_priority> q;
	q.push(initial_state);
	while (!q.empty()) {
		state_t current_state = q.top();
		q.pop();
		if (current_state.heuristic_val == 0) {
			cout << current_state.cost << endl;
			return;
		}
		pair<short, short> next_moves[] = {{0, -1}, {0, 1}, { -1, 0}, {1, 0}};
		for (auto i = 0; i < 4; ++i) {
			generate_state(q, current_state, next_moves[i]);
		}
	}

}


int main() {
	short init_data[grid_size][grid_size];
	short init_zero_pos;
	short target_data[grid_size][grid_size];
	for (auto i = 0; i < grid_size; ++i) {
		for (auto j = 0; j < grid_size; ++j) {
			short grid_val;
			cin >> grid_val;
			if (grid_val == 0) {
				init_zero_pos = i * grid_size + j;
			}
			init_data[i][j] = grid_val;
			target_data[i][j] = (i * grid_size + j + 1) % (grid_size * grid_size);
		}
	}
	state_t initial_state(init_data);
	initial_state.zero_pos = init_zero_pos;
	initial_state.update_heuristic();
	initial_state.cost = 0;
	state_t target(target_data);
	target.zero_pos = grid_size * grid_size - 1;
	bfs(initial_state, target);
}


Measured memory_bytes: 174768