CF1182F Maximum Sine

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.

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.