分数: 625 点
问题陈述
给你正整数 A,B,C,D 满意 \displaystyle \frac AB < \frac CD.
找到最小的正整数 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
考虑第一个测试用例。
例如,如果 p=5,q=3,然后 \displaystyle \frac32<\frac53<\frac21,所以 q=3 满足条件。
没有小于的正整数 3 满足条件 q,所以第一个测试用例的答案是 3.