최대 사인값

정수 $a$, $b$, $p$, $q$가 주어진다. 함수 $f(x) = |\sin(\frac{p}{q} \pi x)|$를 정의한다. $a \le x \le b$를 만족하는 정수 $x$ 중에서 $f(x)$를 최대로 하는 가장 작은 정수 $x$를 구한다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 한 줄이며, 정수 $a$, $b$, $p$, $q$ ($0 \le a \le b \le 10^{9}$, $1 \le p, q \le 10^{9}$)가 주어진다.

각 테스트 케이스마다 $f(x)$를 최대로 하는 가장 작은 정수 $x$를 한 줄에 하나씩 출력한다.

첫 번째 테스트 케이스에서 $f(0) = 0$, $f(1) = f(2) \approx 0.866$, $f(3) = 0$이다. 두 번째 테스트 케이스에서 $f(55) \approx 0.999969$이며, 이는 모든 후보 중 가장 큰 값이다.