Infinite Garden (Small)

The king of the Kingdom of Pascal loves mazes. One day he ordered a retainer to build a maze that covers the wide garden of the castle. That was a hard order, because the castle garden is infinitely wide. Put the origin at the castle, let the $X$ axis point east and the $Y$ axis point north. The garden is then the whole region with $X \ge 0$ and $Y \ge 0$.

You are an excellent robotics engineer, and you rebuilt a gardening robot into a robot that draws a maze in the garden. The robot has two modes, A and B, a tape holding a row of the characters L, X and R, and a read head that points at one cell of the tape. The robot reads the character under the head and changes how it moves. The head only moves in one direction, from the front of the tape toward the back, but the robot keeps reading by copying the whole tape, including the part it has already read, and appending the copy to the end. The robot can also rewrite any cell of the tape.

The robot repeats the following steps in order.

1. If the head points at the last character of the tape, the robot does one of the following, depending on its mode.
   • In mode A it rewrites the first character of the tape, X to L and L to X. Then it copies the whole tape, swaps L and R in the copy, and appends the copy to the end of the tape. Then it switches to mode B.
   • In mode B it copies the whole tape, reverses the copy, and appends it to the end of the tape. Then it switches to mode A.
2. It moves a distance of 2 in the direction it faces and advances the head by one cell.
3. It reads the character under the head. On L it turns 90 degrees left, on R it turns 90 degrees right, on X it keeps its direction.

Place the robot at $(1, 1)$, face it in the positive $Y$ direction, and give it a tape holding the single character X. The robot starts in mode A with the head on that X. Once it is switched on, the robot runs through the garden forever. Take the track the robot leaves as the walls of the maze, and a complicated maze appears. The king praised you for this.

The figure shows the first eight moves of the robot and the state changes along the way. The character in brackets on the tape is the cell the head points at. Starting from $(1, 1)$, the robot extends the tape at once, goes straight north for a distance of 2, and turns east.

A maze so complicated that nobody can get out of it is a problem of its own. The king ordered you to verify the maze the robot drew, so you decided to write a program that computes the shortest distance between two given points inside the maze.

A path used to measure distance consists only of segments parallel or perpendicular to the $X$ axis. A path may not leave the garden and may not cross a wall. Walls have zero thickness, so a path may run arbitrarily close to the line a wall lies on. The shortest distance between two points is the greatest lower bound of the lengths of such paths, and it is always an integer.

The first line holds the number of test cases $T$. Each of the next $T$ lines holds four even integers $P_x$, $P_y$, $Q_x$ and $Q_y$, separated by spaces.

Neither $(P_x, P_y)$ nor $(Q_x, Q_y)$ has a wall on it, because every point on a wall has at least one odd coordinate.

Constraints

• $1 \le T \le 100$
• $0 \le P_x, P_y, Q_x, Q_y \le 32$
• $P_x$, $P_y$, $Q_x$ and $Q_y$ are all even.

For each test case, print one line in the following format.

Case #x: y

Here $x$ is the test case number starting at 1, and $y$ is the shortest distance from $P$ to $Q$ along a path defined above.