

Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
\displaystyle \frac AB < \frac CD を満たす正整数 A,B,C,D が与えられます。
以下の条件を満たす最小の正整数 q を求めてください。
- ある正整数 p が存在し、 \displaystyle \frac AB <\frac pq < \frac CD が成立する。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le A,B,C,D\le 10^{18}
- \displaystyle\frac AB < \frac CD
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T \text{case}_1 \text{case}_2 \vdots \text{case}_T
ただし、 \text{case}_i は i 個目のテストケースを表す。
各テストケースは以下の形式で与えられる。
A B C D
出力
T 行出力せよ。 i 行目には i 番目のテストケースの答えを出力せよ。
入力例 1
5 3 2 2 1 5 2 8 3 1 2 2 1 60 191 11 35 40 191 71 226
出力例 1
3 5 1 226 4
1 番目のテストケースについて考えます。
例えば p=5,q=3 とすると \displaystyle \frac32<\frac53<\frac21 が成立するので q=3 は条件を満たすことが分かります。
3 未満の正整数で条件を満たす q は存在しないので、 1 番目のテストケースの答えは 3 になります。
Score : 625 points
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.
Sample Input 1
5 3 2 2 1 5 2 8 3 1 2 2 1 60 191 11 35 40 191 71 226
Sample Output 1
3 5 1 226 4
Consider the first test case.
For example, if p=5,q=3, then \displaystyle \frac32<\frac53<\frac21, so q=3 satisfies the condition.
There is no positive integer less than 3 that satisfies the condition for q, so the answer for the first test case is 3.