K. Kickshot Tournament
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Kickshot Tournament, part of the prestigious International Cue & Pocket Championship (ICPC) ! This year is a special year because they decide to host the tournament in the virtual world instead of real life !

You are playing on a rectangular pool table of size $$$(R - 1) \times (C - 1)$$$. On every lattice point of the table lies a virtual coin, forming a total of $$$R \times C$$$ coins. The coordinate system is $$$1$$$-indexed, with the coin at row $$$1$$$, column $$$1$$$ positioned at the bottom-left corner. Rows increase upward, and columns increase to the right.

A ball is placed on the coin located at row $$$M$$$, column $$$N$$$, and is shot at a perfect $$$45^\circ$$$ angle in the up-right direction. Initially, for each millisecond, the ball moves one unit upward (toward larger row numbers) and one unit rightward (toward larger column numbers). When the ball hits the top or bottom wall, it flips its vertical direction; when it hits the left or right wall, it flips its horizontal direction. There is no energy loss — the ball continues bouncing perfectly until it lands in one of the four corner pockets.

Each time the ball passes through a coin, that coin immediately disappears from the table. Collecting a coin does not affect the trajectory of the ball. The coin at row $$$M$$$ column $$$N$$$ is immediately collected when shot. The process continues until the ball reaches a corner, where it finally stops.

Your task is to determine how many coins the ball collects in total, including both the starting coin and the final coin at the pocket.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

For each test case, there is one line that contains four integers $$$M$$$, $$$N$$$, $$$R$$$, and $$$C$$$ $$$(3 \le R,C \le 10^9, 1 \le M \lt R, 1 \le N \lt C, (M,N) \neq (1,1))$$$ indicating the starting position of the ball and the size of the table.

Output

For each test case, output one line that contains a single integer $$$X$$$ — the number of coins the ball collects.

If the ball never reaches any of the corners, output $$$-1$$$.

Example
Input
3
3 4 6 8
2 3 6 7
4 3 7 10
Output
17
5
-1
Note

The first testcase can be visualized as follows:

The ball path.