Minimum Knight Moves

Given two positions on a standard chessboard, determine the minimum number of moves a knight requires to move from the starting position to the ending position. The chessboard follows the coordinate system where each coordinate \(x, y\) satisfies \(0 \leq x < 8\) and \(0 \leq y < 8\). If either the start or end position is outside this boundary, the program should output "Invalid input".

The knight moves in an "L" shape: it can move two squares in one direction and then one square perpendicular to that. This can be represented by the eight possible moves: \((\pm2, \pm1)\) and \((\pm1, \pm2)\).

Your task is to compute the minimum number of moves required to reach from the start to the end. You are provided with the starting coordinate and ending coordinate as input from standard input (stdin) and you should write the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains two space-separated integers representing the starting position (x) and (y). The second line contains two space-separated integers representing the ending position (x) and (y).

outputFormat

Output a single line containing the minimum number of moves required for the knight to reach the ending position from the starting position. If either of the positions is outside the range (0 \leq x, y < 8), output "Invalid input".## sample

4 4
4 4

0