Maximum Sine

Description:

Input:

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}$$$).

Output:

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

Sample Input:

2
0 3 1 3
17 86 389 995

Sample Output:

1
55

Note:

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.