Maximum Sine

求 $[a, b]$ 中使得 $f(x)\! =\!\left|\sin\!\left(\frac{p}{q}\pi x\right)\right|$ 取得最大值的整数 $x$。且 $x$ 可能有多个取值，请输出符合条件的最小的 $x$。

You have given integers $ a $ , $ b $ , $ p $ , and $ q $ . Let $ f(x) = \text{abs}(\text{sin}(\frac{p}{q} \pi x)) $ . Find minimum possible integer $ x $ that maximizes $ f(x) $ where $ a \le x \le b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains four integers $ a $ , $ b $ , $ p $ , and $ q $ ( $ 0 \le a \le b \le 10^{9} $ , $ 1 \le p $ , $ q \le 10^{9} $ ).

Print the minimum possible integer $ x $ for each test cases, separated by newline.

2
0 3 1 3
17 86 389 995

1
55

In the first test case, $ f(0) = 0 $ , $ f(1) = f(2) \approx 0.866 $ , $ f(3) = 0 $ . In the second test case, $ f(55) \approx 0.999969 $ , which is the largest among all possible values.