您已给出整数 $$$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$$$,这是所有可能值中最大的。