Infinite Garden (Large)

The king of the Pascal Kingdom loves mazes. One day he ordered a retainer to build a maze that covers the wide garden of his 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 then covers the whole region with $X \ge 0$ and $Y \ge 0$.

You are a fine robotics engineer, and you rebuilt a gardening robot into a robot that draws a maze on the garden. The robot has two modes, A and B, a tape on which the characters "L", "X" and "R" are written one after another, and a read head that points at one cell of the tape. The robot reads the character under the read head and changes its motion accordingly. The read head only moves forward, from the front of the tape to the back, but the robot can copy the whole tape, including the part it has already read, and append the copy to the end of the tape, so it always has more tape to read. The robot can also rewrite any cell of the tape.

The robot repeats the following steps in order.

• If the read head points at the last character of the tape, the robot does one of the following, depending on its mode.

  • In mode A, the robot rewrites the first character of the tape: "X" becomes "L", and "L" becomes "X". Then it copies the whole tape, replaces "L" with "R" and "R" with "L" inside the copy, and appends the copy to the end of the tape. Then it switches to mode B.
  • In mode B, the robot copies the whole tape, reverses the copy front to back, and appends it to the end of the tape. Then it switches to mode A.

• The robot moves forward a distance of 2 and advances the read head by one cell.

• The robot reads the character under the read head. On "L" it turns 90 degrees to the left, on "R" it turns 90 degrees to the right, and on "X" it does nothing.

Place the robot at coordinates $(1, 1)$ facing the positive direction of the $Y$ axis, and give it a tape holding the single character "X". At the start the robot is in mode A and the read head points at that "X". Switch the robot on and it runs through the garden forever. Taking the trail of the robot as the walls of a maze gives a complicated maze. The king praised you for this work.

Figure: the first eight steps of the robot and how its state changes. The character wrapped in "[]" on the tape is the one the read head points at.

The figure shows how the robot behaves at the beginning. Starting from $(1, 1)$, the robot immediately appends to the tape, runs straight north for a length of 2, and turns east. After that it proceeds as drawn in the figure.

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

The program reads the coordinates of two points $P$ and $Q$ and prints the shortest distance between them inside the maze. To keep things simple, a route used to measure distance consists only of segments parallel or perpendicular to the $X$ axis. Walls cannot be crossed, but a wall itself is infinitely thin, so the route may come arbitrarily close to the line a wall lies on. The shortest distance defined this way is always an integer.

The first line holds a positive integer $T$, the number of test cases. The next $T$ lines hold one test case each.

Each test case is one line of four even integers separated by spaces. In order they are $P_x$, $P_y$, $Q_x$, $Q_y$.

Both $(P_x, P_y)$ and $(Q_x, Q_y)$ are points where the maze has no wall. That is clear because every point on a wall of the maze has at least one odd coordinate.

Constraints

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

For each test case, print one line of the form

Case #X: L

where $X$ is the test case number starting from 1, and $L$ is the shortest distance from $P$ to $Q$ along a route as defined above.