### BUGGY CODE ###

import heapq

CORRECT = 0x0fedcba987654321
heap_puzzle = []
cache = {}


class Puzzle:
    DEST_BOARD_DICT = {CORRECT >> (4 * i) & 0b1111: i for i in range(16)}
    HEURISTICS = tuple(
            tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16)) for orig in range(16))

    def __init__(self, board, pid0, count, prev, heuristic=None):
        self.board = board
        self.pid0 = pid0
        self.count = count
        self.prev = prev
        self.invalid = False
        self.heuristic = heuristic

    def swap(self, dest):
        global OFFSET_MASTER, SWAP_VALUE_MASTER
        dest_val = (self.board >> OFFSET_MASTER[dest]) & 0b1111
        return self.board + dest_val * SWAP_VALUE_MASTER[self.pid0][dest]

    def get_sum_heuristic(self):
        if self.heuristic is not None:
            return self.heuristic

        orig_board_dict = {i: self.board >> (4 * i) & 0b1111 for i in range(16)}
        self.heuristic = sum(self.HEURISTICS[pid][self.DEST_BOARD_DICT[val]] for pid, val in orig_board_dict.items())

        return self.heuristic

    def __lt__(self, other):
        return False


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    global MOVE_CANDIDATE

    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    global OFFSET_MASTER, SWAP_CANDIDATE
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def put_next_puzzle():
    global heap_puzzle, cache
    (cost, puzzle) = heapq.heappop(heap_puzzle)
    if puzzle.invalid:
        return -1
    board, pid0, count, prev = puzzle.board, puzzle.pid0, puzzle.count, puzzle.prev
    for new_pid0 in SWAP_CANDIDATE[pid0]:
        if new_pid0 == prev:
            continue

        new_board = puzzle.swap(new_pid0)

        if new_board == CORRECT:
            return count + 1

        heuristic = None
        if new_board in cache:
            closed_puzzle = cache[new_board]
            if closed_puzzle.count <= count:
                continue
            else:
                closed_puzzle.invalid = True
                heuristic = closed_puzzle.heuristic

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                pid0=new_pid0,
                prev=pid0,
                heuristic=heuristic
        )
        new_cost = count + 1 + new_puzzle.get_sum_heuristic()
        heapq.heappush(heap_puzzle, (new_cost, new_puzzle))
        cache[new_board] = new_puzzle
    return -1


first_board = 0
first_pid0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        first_board += v << get_offset(i, j)
        if v == 0:
            first_pid0 = 4 * j + i

s_puzzle = Puzzle(board=first_board, count=0, pid0=first_pid0, prev=-1)
heapq.heappush(heap_puzzle, (s_puzzle.get_sum_heuristic(), s_puzzle))
cache[first_board] = s_puzzle
result = None

while True:
    result = put_next_puzzle()
    if result > -1:
        break

print(result)

### FIXED CODE ###

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 = 0xfedcba9876543210

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))