Вам даны числа \(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\).
В первом примере, \(f(0) = 0\), \(f(1) = f(2) \approx 0.866\), \(f(3) = 0\).
Во втором примере, \(f(55) \approx 0.999969\), которое максимально возможное число среди всех возможных чисел.
2 0 3 1 3 17 86 389 995
1 55
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач