Welcome to ZOJ
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.

c{n}-d\left\lfloor{\frac{a}{b}n}\right\rfloor

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