Maximum Sine

You are given integers $a$, $b$, $p$, and $q$. Let $f(x) = |\sin(\frac{p}{q} \pi x)|$. Find the minimum integer $x$ that maximizes $f(x)$ over all integers $x$ with $a \le x \le b$.

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

For each test case, print the minimum integer $x$ that maximizes $f(x)$, one per line.

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