Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Maximum Sine

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

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.

Example

Input

2 0 3 1 3 17 86 389 995

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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/18/2019 21:20:03 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|