Problem Statement

You are given positive integers $A,B,C,D$ satisfying $\displaystyle \frac AB < \frac CD$.

Find the smallest positive integer $q$ satisfying the following condition:

• There exists a positive integer $p$ such that $\displaystyle \frac AB <\frac pq < \frac CD$.

$T$ test cases are given, so solve each.

Constraints

• $1\le T\le 2\times 10^5$
• $1\le A,B,C,D\le 10^{18}$
• $\displaystyle\frac AB < \frac CD$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Here, $\text{case}_i$ represents the $i$-th test case.

Each test case is given in the following format:

A B C D

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.