F. Максимальный синус
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны числа $$$a$$$, $$$b$$$, $$$p$$$ и $$$q$$$. Пусть $$$f(x) = \text{abs}(\text{sin}(\frac{p}{q} \pi x))$$$.

Найдите минимальное возможное целое число $$$x$$$, которое максимизирует $$$f(x)$$$, где $$$a \le x \le b$$$.

Входные данные

Каждый тест содержит несколько тестовых случаев.

Первая строка содержит одно целое число $$$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}$$$).

Выходные данные

Для каждого теста в новой строке выведите минимально возможно целое число $$$x$$$.

Пример
Входные данные
2
0 3 1 3
17 86 389 995
Выходные данные
1
55
Примечание

В первом примере, $$$f(0) = 0$$$, $$$f(1) = f(2) \approx 0.866$$$, $$$f(3) = 0$$$.

Во втором примере, $$$f(55) \approx 0.999969$$$, которое максимально возможное число среди всех возможных чисел.