Knight's Minimum Moves

Given an 8x8 chessboard, determine the minimum number of moves a knight requires to travel from a starting coordinate to a target coordinate.

The knight moves in an L-shape. In each move, it can change its position by one of the following offsets: \( (2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2) \). The board positions are numbered from 1 to 8 in both dimensions.

Solve the problem using a Breadth-First Search (BFS) approach to ensure that the minimum number of moves is found for each test case.

inputFormat

The first line contains an integer ( T ) (( T \geq 1 )) indicating the number of test cases. Each of the following ( T ) lines contains four space-separated integers: ( start_x ), ( start_y ), ( target_x ), and ( target_y ), representing the starting and target positions of the knight.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of moves required for the knight to reach the target position.## sample

3
1 1 8 8
1 1 2 2
3 3 4 3

6
4
3