Problem: 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

Solution (in PYTHON3):

Solution:
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
    # Never reaches here.
    return False


if __name__ == "__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)
    )

    adjacent = (
        (1, 4),          # 0
        (0, 2, 5),       # 1
        (1, 3, 6),       # 2
        (2, 7),          # 3
        (0, 5, 8),       # 4
        (1, 4, 6, 9),    # 5
        (2, 5, 7, 10),   # 6
        (3, 6, 11),      # 7
        (4, 9, 12),      # 8
        (5, 8, 10, 13),  # 9
        (6, 9, 11, 14),  # 10
        (7, 10, 15),     # 11
        (8, 13),         # 12
        (9, 12, 14),     # 13
        (10, 13, 15),    # 14
        (11, 14)         # 15
    )

    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