G - A/B < p/q < C/D Editorial /

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.