Floor Function

Time Limit: 10 Seconds
Memory Limit: 65536 KB

`a`, `b`, `c` and `d` are all positive integers
which satisfy `bc` - `ad` > 0.
Your task is to minimize the following function of a positive integer `n`.

⌊`x`⌋, the floor function, means the largest integer not greater than `x`.

You need to find a positive integer `n` to minimize the above function.
If there are multiple `n`'s minimizing it, find the smallest one.

#### Input

There are multiple test cases.
The first line of input contains an integer `T` ≈ 100000
indicating the number of test cases. For each test case:

There are four positive integers: `a`, `b`, `c` and `d`.
(1 <= `a, b, c, d` <= 10^{18})

#### Output

For each case, print the smallest positive integer `n` which minimizes the function.

#### Sample Input

3
1 2 3 4
3 4 4 5
97 37 101 31

#### Sample Output

2
4
1

Author:

**ZHOU, Yuchen**
Source:

**The 12th Zhejiang Provincial Collegiate Programming Contest**
Submit
Status