Connect the Dots

A well known puzzle asks you to connect 9 dots on a sheet of paper with 4 straight line segments without lifting the pencil. Simone has built a game called "Connect the Dots" around a generalisation of that puzzle.

In Connect the Dots the dots form a 4 × 4 grid with equal spacing between rows and between columns. Each dot has a distinct number from 1 to 16. Your task is to connect the dots in the order of their numbers, starting at dot 1 and ending at dot 16.

The pencil never leaves the paper and draws straight line segments one after another. The first segment starts at dot 1, every later segment starts where the previous one ended, and the last segment ends at dot 16. A segment may have any length and any direction, a turning point does not have to be on a dot and may lie outside the grid, and segments may cross or overlap one another.

A dot on a segment counts as visited the moment the pencil passes over it, so you may pass over other dots on the way to the dot you are heading for. For example, visiting the first four dots in the order 1, 4, 2, 3, 2, 4, ... is acceptable. Formally, the sequence 1, 2, ..., 16 must be a subsequence of the sequence of dots visited.

The figure shows one solution for the first sample.

Simone bet you a balloon that the puzzle is too hard. Prove her wrong by writing a program that solves the puzzle for you.

The input consists of 4 lines, each with 4 integers. The j-th integer on the i-th line is the number of the dot in the i-th row and j-th column of the grid.

The 16 numbers are all between 1 and 16 inclusive and pairwise distinct.

Output the minimum number of line segments needed to connect all the dots in order.