Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3873
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 <= 1018)

#### 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