Knight Hop

No attempts yetTime limit2sMemory limit512 MB

Problem

An $8 \times 8$ chessboard is given. Each square is identified by an ordered pair of integers, where each coordinate ranges from $1$ to $8$. For example, in the diagram below piece A is at position $(2, 2)$ and piece B is at position $(4, 3)$.

A knight moves in an "L" pattern: it can leap over other pieces to one of up to eight squares. In the diagram below, K marks the knight's current square and the numbers $1$ through $8$ mark the squares it may move to.

Given the knight's starting square and a target square, compute the minimum number of moves needed to move the knight from the start to the target. The knight may never leave the board.

Input

Four integers, each between $1$ and $8$. The first two give the knight's starting position; the last two give the target position.

Output

Output the minimum number of moves (a non-negative integer) required to move the knight from the start to the target. The knight must not leave the board at any point during the sequence of moves.