← 返回题目列表

Codeforces · 1182/F

F. 最大正弦值

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

您已给出整数 $$$a$$$、$$$b$$$、$$$p$$$ 和 $$$q$$$。令 $$$f(x) = \text{abs}(\text{sin}(\frac{p}{q} \pi x))$$$。

找到最大化 $$$f(x)$$$ 的最小可能整数 $$$x$$$,其中 $$$a \le x \le b$$$。

输入

每个测试包含多个测试用例。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含四个整数 $$$a$$$、$$$b$$$、$$$p$$$ 和 $$$q$$$ ($$$0 \le a \le b \le 10^{9}$$$、$$$1 \le p$$$、$$$q \le 10^{9}$$$)。

输出

打印每个测试用例的最小可能整数 $$$x$$$,以换行符分隔。

示例

输入 #1

2
0 3 1 3
17 86 389 995

输出 #1

1
55

注意

在第一个测试用例中,$$$f(0) = 0$$$, $$$f(1) = f(2) \approx 0.866$$$, $$$f(3) = 0$$$。

在第二个测试用例中,$$$f(55) \approx 0.999969$$$,这是所有可能值中最大的。