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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import heapq
distance = ((0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))

def d_manhattan(node_list):
	s = 0
	for i in range(16):
		j = node_list[i] - 1
		if j == -1:
			continue
		s += distance[i][j]
	return s

def moveNode(node_list, space, direction):
	node_tmp = node_list[:]
	(node_tmp[space], node_tmp[space + direction]) = (node_tmp[space + direction], node_tmp[space])
	return node_tmp

class board:

	def __init__(self, node_list, move):
		self.node = node_list
		self.space = node_list.index(0)
		self.move = move
		self.h = d_manhattan(node_list)
		self.f = self.move + self.h

	def makeBoard(self, node_close):
		node_now = self.node
		space = self.space
		move = self.move
		x_s = space % 4
		y_s = space // 4
		if x_s < 3:
			node_tmp = moveNode(node_now, space, 1)
			if tuple(node_tmp) not in node_close:
				yield board(node_tmp, move + 1)
		if x_s > 0:
			node_tmp = moveNode(node_now, space, -1)
			if tuple(node_tmp) not in node_close:
				yield board(node_tmp, move + 1)
		if y_s < 3:
			node_tmp = moveNode(node_now, space, 4)
			if tuple(node_tmp) not in node_close:
				yield board(node_tmp, move + 1)
		if y_s > 0:
			node_tmp = moveNode(node_now, space, -4)
			if tuple(node_tmp) not in node_close:
				yield board(node_tmp, move + 1)
b_open = []
n_close = set()
n_goal = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
n_start = []
for i in range(4):
	inp = list(map(int, input().split()))
	n_start.extend(inp)
b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))
i = 0
while b_open:
	(_, _, _, b_now) = heapq.heappop(b_open)
	if b_now.node == n_goal:
		b_goal = b_now
		break
	n_close.add(tuple(b_now.node))
	for b_new in b_now.makeBoard(n_close):
		heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
		i += 1
print(b_goal.move)


distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def get_distance(board):
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def df_lower_search(limit, move, space, lower, pre_p):
	if move == limit:
		if board == GOAL:
			return True
	else:
		for i in adjacent[space]:
			p = board[i]
			if p == pre_p:
				continue
			board[space] = p
			board[i] = 0
			new_lower = lower - distance[p][i] + distance[p][space]
			if new_lower + move <= limit:
				if df_lower_search(limit, move + 1, i, new_lower, p):
					return True
			board[space] = 0
			board[i] = p
import sys
board = list(map(int, sys.stdin.read().split()))
s = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)
n = get_distance(board)
if e_o[s] != n % 2:
	n += 1
for l in range(n, 46, 2):
	if df_lower_search(l, 0, s, n, None):
		print(l)
		break


distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def get_distance(board):
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
import sys
import heapq

def solve():
	board = list(map(int, sys.stdin.read().split()))
	h_cost = get_distance(board)
	state = [h_cost, board]
	q = [state]
	d = {tuple(board): True}
	while q:
		state1 = heapq.heappop(q)
		(h_cost, board) = state1
		if board == GOAL:
			return h_cost
		space = board.index(0)
		for i in adjacent[space]:
			p = board[i]
			new_board = board[:]
			(new_board[space], new_board[i]) = (p, 0)
			new_h_cost = h_cost + 1 - distance[p][i] + distance[p][space]
			key = tuple(new_board)
			if key not in d and new_h_cost <= 45:
				new_state = [new_h_cost, new_board]
				heapq.heappush(q, new_state)
				d[key] = True
print(solve())


from sys import stdin
readline = stdin.readline
GOAL = [i for i in range(1, 16)] + [0]
MAX_DEPTH = 45
count = 0
adjacent = ((1, 4), (0, 2, 5), (1, 6, 3), (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))
distance = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def manhattan_distance(board):
	return sum((distance[bi][i] for (i, bi) in enumerate(board)))

def answer_is_odd(board):
	return sum(divmod(board.index(0), 4)) % 2

def search(board):
	lower = manhattan_distance(board)
	start_depth = lower
	if lower % 2 ^ answer_is_odd(board):
		start_depth += 1
	for limit in range(start_depth, MAX_DEPTH + 1, 2):
		id_lower_search(board, limit, 0, board.index(0), None, lower)
		if count > 0:
			return limit

def nxt_board(board, space, prev):
	for nxt in adjacent[space]:
		if nxt == prev:
			continue
		b = board[:]
		(b[space], b[nxt]) = (b[nxt], 0)
		yield (b, nxt)

def id_lower_search(board, limit, move, space, prev, lower):
	if move == limit:
		if board == GOAL:
			global count
			count += 1
	else:
		for (b, nxt) in nxt_board(board, space, prev):
			p = board[nxt]
			new_lower = lower - distance[p][nxt] + distance[p][space]
			if new_lower + move <= limit:
				id_lower_search(b, limit, move + 1, nxt, space, new_lower)

def main():
	start = (map(int, readline().split()) for _ in range(4))
	start = [y for x in start for y in x]
	print(search(start))
main()


distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def get_distance(board):
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def df_lower_search(limit, move, space, lower, pre_p):
	if move == limit:
		if board == GOAL:
			return True
	else:
		for i in adjacent[space]:
			p = board[i]
			if p == pre_p:
				continue
			board[space] = p
			board[i] = 0
			new_lower = lower - distance[p][i] + distance[p][space]
			if new_lower + move <= limit:
				if df_lower_search(limit, move + 1, i, new_lower, p):
					return True
			board[space] = 0
			board[i] = p
import sys
board = list(map(int, sys.stdin.read().split()))
n = get_distance(board)
for l in range(n, 46):
	if df_lower_search(l, 0, board.index(0), n, None):
		print(l)
		break


distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def get_distance(board):
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def df_lower_search(limit, move, space, lower, pre_p):
	if move == limit:
		if board == GOAL:
			return True
	else:
		for i in adjacent[space]:
			p = board[i]
			if p == pre_p:
				continue
			board[space] = p
			board[i] = 0
			new_lower = lower - distance[p][i] + distance[p][space]
			if new_lower + move <= limit:
				if df_lower_search(limit, move + 1, i, new_lower, p):
					return True
			board[space] = 0
			board[i] = p
import sys
board = list(map(int, sys.stdin.read().split()))
s = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)
n = get_distance(board)
if e_o[s] != n % 2:
	n += 1
for l in range(n, 46, 2):
	if df_lower_search(l, 0, s, n, None):
		print(l)
		break


from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = ((1, 4), (0, 2, 5), (1, 6, 3), (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))
distance = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))

def get_diff(B):
	diff = 0
	for (i, v) in enumerate(B):
		diff += distance[v][i]
	return diff

def get_next_board(board, space, prev):
	for nxt in neighbor[space]:
		if nxt == prev:
			continue
		b = board[:]
		(b[space], b[nxt]) = (b[nxt], 0)
		yield (b, nxt)

def answer_is_odd(board):
	return sum(divmod(board.index(0), 4)) % 2

def search(board):
	lower = get_diff(board)
	start_depth = lower
	if lower % 2 ^ answer_is_odd(board):
		start_depth += 1
	for limit in range(start_depth, MAX_DEPTH + 1, 2):
		get_next(board, limit, 0, board.index(0), None, lower)
		if count > 0:
			return limit

def get_next(board, limit, move, space, prev, lower):
	if move == limit:
		if board == solution:
			global count
			count += 1
	else:
		for (b, nxt) in get_next_board(board, space, prev):
			p = board[nxt]
			new_lower = lower - distance[p][nxt] + distance[p][space]
			if new_lower + move <= limit:
				get_next(b, limit, move + 1, nxt, space, new_lower)
boad = []
for i in range(4):
	boad.extend(map(int, input().split()))
print(search(boad))
exit()


from collections import deque
import heapq

def move(P, p):
	if p > 3:
		tmp = P[:]
		(tmp[p], tmp[p - 4]) = (tmp[p - 4], tmp[p])
		tmpp = p - 4
		yield (tmp, tmpp)
	if p < 12:
		tmp = P[:]
		(tmp[p], tmp[p + 4]) = (tmp[p + 4], tmp[p])
		tmpp = p + 4
		yield (tmp, tmpp)
	if p % 4 > 0:
		tmp = P[:]
		(tmp[p], tmp[p - 1]) = (tmp[p - 1], tmp[p])
		tmpp = p - 1
		yield (tmp, tmpp)
	if p % 4 < 3:
		tmp = P[:]
		(tmp[p], tmp[p + 1]) = (tmp[p + 1], tmp[p])
		tmpp = p + 1
		yield (tmp, tmpp)

def evaluate(P, Q):
	mht = 0
	for i in range(16):
		pi = P.index(i)
		qi = Q.index(i)
		(pc, pr) = (pi // 4, pi % 4)
		(qc, qr) = (qi // 4, qi % 4)
		mht += abs(pc - qc) + abs(pr - qr)
	return mht
A = []
B = [int(i) % 16 for i in range(1, 17)]
for i in range(4):
	A += [int(i) for i in input().split()]
dp = {str(A): (1, 0), str(B): (2, 0)}
h = [(evaluate(A, B), A, 0, A.index(0))]
e = [(evaluate(A, B), B, 0, 15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while len(h) > 0 and len(e) > 0:
	(mht, tmp, count, p) = heapq.heappop(h)
	if sw and len(h) > 0:
		tmph = (mht, tmp, count, p)
		(mht, tmp, count, p) = heapq.heappop(h)
		heapq.heappush(h, tmph)
		sw = True
	elif sw:
		sw = False
	for (i, j) in move(tmp, p):
		key = str(i)
		if key in dp:
			if dp[key][0] == 2:
				tmpcount = count + 1 + dp[key][1]
				if tmpcount < ans:
					ans = tmpcount
			else:
				continue
		else:
			dp[key] = (1, count + 1)
			mht = evaluate(B, i)
			if count + mht * 14 // 13 < ans:
				heapq.heappush(h, (mht // 2 + count, i, count + 1, j))
	(_, tmp, count, p) = heapq.heappop(e)
	for (i, j) in move(tmp, p):
		key = str(i)
		if key in dp:
			if dp[key][0] == 1:
				tmpcount = count + 1 + dp[key][1]
				if tmpcount < ans:
					ans = tmpcount
			else:
				continue
		else:
			dp[key] = (2, count + 1)
			mht = evaluate(A, i)
			if count + mht * 14 // 13 < ans:
				heapq.heappush(e, (mht // 2 + count, i, count + 1, j))
if str(A) == '[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]':
	ans = 0
print(ans)


from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = ((1, 4), (0, 2, 5), (1, 6, 3), (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))
distance = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))

def get_diff(B):
	return sum([distance[v][i] for (i, v) in enumerate(B)])

def get_next_board(board, space, prev):
	for nxt in neighbor[space]:
		if nxt == prev:
			continue
		b = board[:]
		(b[space], b[nxt]) = (b[nxt], 0)
		yield (b, nxt)

def answer_is_odd(board):
	return sum(divmod(board.index(0), 4)) % 2

def search(board):
	lower = get_diff(board)
	start_depth = lower
	if lower % 2 ^ answer_is_odd(board):
		start_depth += 1
	for limit in range(start_depth, MAX_DEPTH + 1, 2):
		get_next(board, limit, 0, board.index(0), None, lower)
		if count > 0:
			return limit

def get_next(board, limit, move, space, prev, lower):
	global count
	if move == limit:
		if board == solution:
			count += 1
	else:
		for (b, nxt) in get_next_board(board, space, prev):
			p = board[nxt]
			new_lower = lower - distance[p][nxt] + distance[p][space]
			if new_lower + move <= limit:
				get_next(b, limit, move + 1, nxt, space, new_lower)
boad = [int(a) for _ in range(4) for a in stdin.readline().split()]
print(search(boad))


from heapq import heappop, heappush
manhattan = ((0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))
movables = ((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))
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, input().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


from heapq import heappop, heappush
manhattan = [[abs(i % 4 - j % 4) + abs(i // 4 - j // 4) for j in range(16)] for i in range(16)]
movables = [{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}]
swap_cache = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 18364758544493064720

def swap(board, move_from, move_to):
	return board + swap_cache[move_from][move_to] * (15 - (board >> 4 * move_from & 15))
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, input().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		new_board = swap(board, new_blank, blank)
		if new_board in visited:
			continue
		num = board >> 4 * new_blank & 15
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = ((1, 4), (0, 2, 5), (1, 6, 3), (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))
distance = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))

def get_diff(B):
	return sum((distance[v][i] for (i, v) in enumerate(B)))

def get_next_board(board, space, prev):
	for nxt in neighbor[space]:
		if nxt == prev:
			continue
		b = board[:]
		(b[space], b[nxt]) = (b[nxt], 0)
		yield (b, nxt)

def answer_is_odd(board):
	return sum(divmod(board.index(0), 4)) % 2

def search(board):
	lower = get_diff(board)
	start_depth = lower
	if lower % 2 ^ answer_is_odd(board):
		start_depth += 1
	for limit in range(start_depth, MAX_DEPTH + 1, 2):
		get_next(board, limit, 0, board.index(0), None, lower)
		if count > 0:
			return limit

def get_next(board, limit, move, space, prev, lower):
	if move == limit:
		if board == solution:
			global count
			count += 1
	else:
		for (b, nxt) in get_next_board(board, space, prev):
			p = board[nxt]
			new_lower = lower - distance[p][nxt] + distance[p][space]
			if new_lower + move <= limit:
				get_next(b, limit, move + 1, nxt, space, new_lower)
print(search([int(a) for _ in range(4) for a in stdin.readline().split()]))


from sys import stdin
from heapq import heappop, heappush
manhattan = [[abs(i % 4 - j % 4) + abs(i // 4 - j // 4) for j in range(16)] for i in range(16)]
movables = ((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))
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, stdin.readline().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))

def get_distance(board):
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
import sys
import heapq

def solve():
	board = list(map(int, sys.stdin.read().split()))
	h_cost = get_distance(board)
	state = (h_cost, board)
	q = [state]
	d = {tuple(board): True}
	while q:
		state1 = heapq.heappop(q)
		(h_cost, board) = state1
		if board == GOAL:
			return h_cost
		space = board.index(0)
		for i in adjacent[space]:
			p = board[i]
			new_board = board[:]
			(new_board[space], new_board[i]) = (p, 0)
			new_h_cost = h_cost + 1 - distance[p][i] + distance[p][space]
			key = tuple(new_board)
			if key not in d and new_h_cost <= 45:
				new_state = (new_h_cost, new_board)
				heapq.heappush(q, new_state)
				d[key] = True
print(solve())


from heapq import heappop, heappush
manhattan = [[abs(i % 4 - j % 4) + abs(i // 4 - j // 4) for j in range(16)] for i in range(16)]
movables = [{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}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, input().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


from heapq import heappop, heappush
manhattan = ((0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))
movables = ((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))
swap_mul = tuple((tuple(((1 << mf) - (1 << mt) for mt in range(0, 64, 4))) for mf in range(0, 64, 4)))
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, input().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


from heapq import heappop, heappush
manhattan = tuple((tuple((abs(i % 4 - j % 4) + abs(i // 4 - j // 4) for j in range(16))) for i in range(16)))
movables = ((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))
swap_mul = tuple((tuple(((1 << mf) - (1 << mt) for mt in range(0, 64, 4))) for mf in range(0, 64, 4)))
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, input().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))


board = [int(s) for _ in range(4) for s in input().split()]
move_piece = [None] * 46
GOAL = list(range(1, 16)) + [0]

def create_adjacent(h, w):
	adjacent = [[] for _ in range(h * w)]
	for i in range(h * w):
		if i % w != w - 1:
			adjacent[i].append(i + 1)
		if i % w != 0:
			adjacent[i].append(i - 1)
		if i // h < h - 1:
			adjacent[i].append(i + w)
		if i // h > 0:
			adjacent[i].append(i - w)
	return adjacent

def id_search(limit, move, space, lower):
	if move == limit:
		if board == GOAL:
			global count
			count += 1
			print(move)
			exit()
	else:
		for x in adjacent[space]:
			p = board[x]
			if move_piece[move] == p:
				continue
			(board[space], board[x]) = (p, 0)
			move_piece[move + 1] = p
			new_lower = lower - distance[p][x] + distance[p][space]
			if new_lower + move <= limit:
				id_search(limit, move + 1, x, new_lower)
			(board[space], board[x]) = (0, p)

def create_distance(h, w):
	distance = [[0] * h * w for _ in range(h * w)]
	for i in range(h * w):
		if i == 0:
			continue
		(ye, xe) = divmod(i - 1, w)
		for j in range(h * w):
			(y, x) = divmod(j, w)
			distance[i][j] = abs(ye - y) + abs(xe - x)
	return distance

def get_distance(board):
	v = 0
	for x in range(len(board)):
		p = board[x]
		if p == 0:
			continue
		v += distance[p][x]
	return v
adjacent = create_adjacent(4, 4)
distance = create_distance(4, 4)
n = get_distance(board)
count = 0
for x in range(n, 46):
	id_search(x, 0, board.index(0), n)
	if count > 0:
		break


import sys
from heapq import heappop, heappush
adjacent = ((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))
distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))
end = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def get_distance():
	global board
	sum_distance = 0
	for i in range(16):
		if board[i] == 0:
			continue
		sum_distance += distance[board[i]][i]
	return sum_distance

def search(limit, move, space, lower, prev_space):
	global board
	if move == limit:
		if board == end:
			return True
	else:
		for next_space in adjacent[space]:
			if next_space == prev_space:
				continue
			board[space] = board[next_space]
			board[next_space] = 0
			new_lower = lower - distance[board[space]][next_space] + distance[board[space]][space]
			if new_lower + move <= limit:
				if search(limit, move + 1, next_space, new_lower, space):
					return True
			board[next_space] = board[space]
			board[space] = 0
board = []
for _ in range(4):
	board.extend(list(map(int, sys.stdin.readline().strip().split())))
n = get_distance()
first_space = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)
if n % 2 != e_o[first_space]:
	n += 1
for l in range(n, 46, 2):
	if search(l, 0, first_space, n, None):
		print(l)
		break


import sys
from typing import List

def get_distance(board: List[int]) -> int:
	sd = 0
	for i in range(16):
		p = board[i]
		if p == 0:
			continue
		sd += distance[p][i]
	return sd

def df_lower_search(limit: int, move: int, space: int, lower: int, pre_p: int) -> bool:
	global board
	global GOAL
	if move == limit:
		if board == GOAL:
			return True
	else:
		for i in adjacent[space]:
			p = board[i]
			if p == pre_p:
				continue
			board[space] = p
			board[i] = 0
			new_lower = lower - distance[p][i] + distance[p][space]
			if new_lower + move <= limit:
				if df_lower_search(limit, move + 1, i, new_lower, p):
					return True
			board[space] = 0
			board[i] = p
	return False
distance = ((), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1))
adjacent = ((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))
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
board = list(map(int, sys.stdin.read().split()))
s = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)
n = get_distance(board)
if e_o[s] != n % 2:
	n += 1
for l in range(n, 46, 2):
	if df_lower_search(l, 0, s, n, -1):
		print(l)
		break


from heapq import heappop, heappush
from functools import lru_cache

@lru_cache(maxsize=None)
def manhattan(size, i, n):
	if n == 0:
		return 0
	else:
		(dn, mn) = divmod(n - 1, size)
		(di, mi) = divmod(i, size)
		return abs(dn - di) + abs(mn - mi)

class Board:
	__slots__ = ('size', 'nums', 'code', '_hash')

	def __init__(self, size, nums, code=None):
		self.size = size
		self.nums = nums
		self._hash = hash(nums)
		if code is None:
			self.code = sum([manhattan(self.size, i, n) for (i, n) in enumerate(self.nums) if n != i + 1])
		else:
			self.code = code

	def __eq__(self, other):
		return self.code == other.code

	def __lt__(self, other):
		return self.code < other.code

	def __gt__(self, other):
		return self.code > other.code

	def __hash__(self):
		return self._hash

	def same(self, other):
		if other is None:
			return False
		if self.__class__ != other.__class__:
			return False
		for i in range(self.size * self.size):
			if self.nums[i] != other.nums[i]:
				return False
		return True

	def solved(self):
		for i in range(self.size * self.size):
			if self.nums[i] > 0 and self.nums[i] - 1 != i:
				return False
		return True

	def find(self, num):
		for i in range(self.size * self.size):
			if self.nums[i] == num:
				return i
		raise IndexError()

	def move(self, p1, p2):
		nums = list(self.nums)
		(v1, v2) = (nums[p1], nums[p2])
		code = self.code - manhattan(self.size, p1, v1) - manhattan(self.size, p2, v2) + manhattan(self.size, p2, v1) + manhattan(self.size, p1, v2)
		(nums[p1], nums[p2]) = (v2, v1)
		return self.__class__(self.size, tuple(nums), code)

	def moves(self):
		i = self.find(0)
		if i > self.size - 1:
			yield self.move(i, i - self.size)
		if i % self.size > 0:
			yield self.move(i, i - 1)
		if i < self.size * (self.size - 1):
			yield self.move(i, i + self.size)
		if (i + 1) % self.size > 0:
			yield self.move(i, i + 1)

	def __str__(self):
		s = ''
		for i in range(self.size * self.size):
			s += ' {}'.format(self.nums[i])
			if (i + 1) % self.size == 0:
				s += '\n'
		return s

class FifteenPuzzle:

	def __init__(self, board, maxmove):
		self.board = board
		self.maxmove = maxmove
		if not board.solved():
			self.steps = self._solve()
		else:
			self.steps = 0

	def _solve(self):
		bs = []
		checked = set()
		i = 0
		heappush(bs, (self.board.code, self.board.code, i, self.board, 0))
		while len(bs) > 0:
			(w, _, _, b, step) = heappop(bs)
			checked.add(b)
			step += 1
			for nb in b.moves():
				if nb.solved():
					return step
				elif self.maxmove < nb.code + step:
					continue
				elif nb in checked:
					continue
				else:
					i += 1
					heappush(bs, (nb.code + step, nb.code, i, nb, step))
		return -1

def run():
	ns = []
	for i in range(4):
		ns.extend([int(i) for i in input().split()])
	board = Board(4, tuple(ns))
	puzzle = FifteenPuzzle(board, 45)
	print(puzzle.steps)
run()


board = [int(s) for _ in range(4) for s in input().split()]
move_piece = [None] * 46
GOAL = list(range(1, 16)) + [0]

def create_adjacent(h, w):
	adjacent = [[] for _ in range(h * w)]
	for i in range(h * w):
		if i % w != w - 1:
			adjacent[i].append(i + 1)
		if i % w != 0:
			adjacent[i].append(i - 1)
		if i // h < h - 1:
			adjacent[i].append(i + w)
		if i // h > 0:
			adjacent[i].append(i - w)
	return adjacent

def id_search(limit, move, space, lower):
	if move == limit:
		if board == GOAL:
			global count
			count += 1
			print(move)
			exit()
	else:
		for x in adjacent[space]:
			p = board[x]
			if move_piece[move] == p:
				continue
			(board[space], board[x]) = (p, 0)
			move_piece[move + 1] = p
			new_lower = lower - distance[p][x] + distance[p][space]
			if new_lower + move <= limit:
				id_search(limit, move + 1, x, new_lower)
			(board[space], board[x]) = (0, p)

def create_distance(h, w):
	distance = [[0] * h * w for _ in range(h * w)]
	for i in range(h * w):
		if i == 0:
			continue
		(ye, xe) = divmod(i - 1, w)
		for j in range(h * w):
			(y, x) = divmod(j, w)
			distance[i][j] = abs(ye - y) + abs(xe - x)
	return distance

def get_distance(board):
	v = 0
	for x in range(len(board)):
		p = board[x]
		if p == 0:
			continue
		v += distance[p][x]
	return v
adjacent = create_adjacent(4, 4)
distance = create_distance(4, 4)
n = get_distance(board)
count = 0
for x in range(n, 46):
	id_search(x, 0, board.index(0), n)
	if count > 0:
		break


from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = ((1, 4), (0, 2, 5), (1, 6, 3), (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))
distance = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6), (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5), (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4), (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3), (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5), (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4), (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3), (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2), (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4), (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3), (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2), (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1), (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3), (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2), (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1), (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))

def get_diff(B):
	return sum([distance[v][i] for (i, v) in enumerate(B)])

def get_next_board(board, space, prev):
	for nxt in neighbor[space]:
		if nxt == prev:
			continue
		b = board[:]
		(b[space], b[nxt]) = (b[nxt], 0)
		yield (b, nxt)

def answer_is_odd(board):
	return sum(divmod(board.index(0), 4)) % 2

def search(board):
	lower = get_diff(board)
	start_depth = lower
	if lower % 2 ^ answer_is_odd(board):
		start_depth += 1
	for limit in range(start_depth, MAX_DEPTH + 1, 2):
		get_next(board, limit, 0, board.index(0), None, lower)
		if count > 0:
			return limit

def get_next(board, limit, move, space, prev, lower):
	global count
	if move == limit:
		if board == solution:
			count += 1
	else:
		for (b, nxt) in get_next_board(board, space, prev):
			p = board[nxt]
			new_lower = lower - distance[p][nxt] + distance[p][space]
			if new_lower + move <= limit:
				get_next(b, limit, move + 1, nxt, space, new_lower)
boad = []
for i in range(4):
	boad.extend(map(int, stdin.readline().split()))
print(search(boad))


from sys import stdin
from heapq import heappop, heappush
manhattan = tuple([[abs(i % 4 - j % 4) + abs(i // 4 - j // 4) for j in range(16)] for i in range(16)])
movables = ((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))
swap_mul = tuple([[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)])
destination = 18364758544493064720
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
	for n in map(int, stdin.readline().split()):
		if n:
			n -= 1
		else:
			n = 15
			blank_init = i
		board_init += n * 16 ** i
		i += 1
estimation_init = sum((manhattan[i][board_init >> 4 * i & 15] for i in range(16) if i != blank_init))
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
	(estimation, board, blank) = heappop(queue)
	if board in visited:
		continue
	elif board == destination:
		print(estimation)
		break
	visited.add(board)
	for new_blank in movables[blank]:
		num = board >> 4 * new_blank & 15
		new_board = board + swap_mul[new_blank][blank] * (15 - num)
		if new_board in visited:
			continue
		new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
		if new_estimation > 45:
			continue
		heappush(queue, (new_estimation, new_board, new_blank))