← 返回题目列表

AtCoder · abc408_g

G. A/B小于p/q小于C/D

中文机器翻译题面 查看原题

分数: 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.