Knight’s Charge

Program

KNIGHT.C, KNIGHT.CPP, KNIGHT.PAS

The chessboard is an 8 by 8 grid of squares. For the purpose of this problem consider the rows of the chessboard to be numbered from 1 to 8 starting at the top and moving down, and the columns to be numbered from 1 to 8 starting at the left and moving right. Board positions will be identified by (row, column) ordered pairs.

The knight is a chess piece capable of moving exactly two squares in one direction and then one square perpendicularly. The figure on the left below shows the possible moves for a knight located on the board at (4,5). Assuming the board is empty except for a knight, the problem is to determine the minimum number of moves required to move from point A to point B on the board. The figure on the right below shows one possibility for the minimum required three moves to move a knight from (4,5) to (4,4).

Input / Output Specification

The first line of input contains a single integer that specifies the number of test cases in the remainder of the input. Each test case contains 4 integers in the range 1 to 8, delimited by one or more spaces, representing the row and column of the starting position on the board, and the row and column of the destination position, respectively. For each test case, simply output the minimum number of moves required to reach the destination position from the starting position.

Sample Input
2 5 5 4 5

3 1 3 8

Sample Output
3 5