Robot Cleaner 2
View as PDFA robot cleaner is placed on the floor of a rectangular room, surrounded by walls. The floor consists of ~n~ rows and ~m~ columns. The rows of the floor are numbered from ~1~ to ~n~ from top to bottom, and the columns of the floor are numbered from ~1~ to ~m~ from left to right. The cell at the intersection of the ~r~-th row and the ~c~-th column is denoted as ~(r,c)~. The initial position of the robot is ~(r_b, c_b)~.
In one second, the robot moves by ~dr~ rows and ~dc~ columns; that is, after one second, the robot moves from the cell ~(r, c)~ to ~(r + dr, c + dc)~. Initially, ~dr = 1~, ~dc = 1~. If there is a vertical wall (the left or the right wall) in the movement direction, ~dc~ is reflected before the movement, so the new value of ~dc~ is ~-dc~. And if there is a horizontal wall (the upper or lower wall), ~dr~ is reflected before the movement, so the new value of ~dr~ is ~-dr~.
Each second (including the moment before the robot starts moving), the robot cleans every cell lying in the same row or the same column as its position. The job of the robot is to clean the whole floor; that is, each floor cell needs to be cleaned at least once.
Illustration for the first example. The red arc is the robot. A cell with blue color is a cleaned cell. Each second, the robot cleans a row and a column at its position.
Given the floor size ~n~ and ~m~, and the robot's initial position ~(r_b, c_b)~, find the time for the robot to do its job.
Input
Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10^4~). The description of the test cases follows.
A test case consists of only one line, containing four integers ~n~, ~m~, ~r_b~, ~c_b~ (~2 \le n, m \le 100~, ~1 \le r_b \le n~, ~1 \le c_b \le m~) — the sizes of the room and the initial position of the robot.
Output
For each test case, print an integer — the time for the robot to clean the whole floor. It can be shown that eventually each floor cell is cleaned at least once.
Scoring
The total score for this problem is ~500~.
Sample Input 1
5
10 10 6 1
10 10 9 9
9 8 5 6
6 9 2 2
2 2 1 1
Sample Output 1
9
10
9
9
1
Notes
In the first example, the floor has the size of ~10\times 10~. The initial position of the robot is ~(6, 1)~. See the illustration of this example in the problem statement.
In the second example, the floor is the same, but the initial position of the robot is now ~(9, 9)~.
In the third example, the floor has the size ~9 \times 8~. The initial position of the robot is ~(5, 6)~.
In the fourth example, the floor has the size ~6 \times 9~. The initial position of the robot is ~(2, 2)~.
In the last example, the floor has the size ~2 \times 2~. The initial position of the robot is ~(1, 1)~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.