A. Доля успешных попыток
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — опытный участник соревнований Codeforces. Недавно вы обнаружили, что за все время своего участия в раундах Codeforces успели сделать y попыток, из которых x были успешными. Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x / y.

Ваше любимое рациональное число в диапазоне [0;1] — это p / q. Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать свою долю успешных попыток равной p / q?

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

Первая строка содержит одно целое число t (1 ≤ t ≤ 1000) — количество тестов.

Каждая из следующих t строк содержит четыре целых числа x, y, p и q (0 ≤ x ≤ y ≤ 109; 0 ≤ p ≤ q ≤ 109; y > 0; q > 0).

Гарантируется, что p / q — несократимая дробь.

Взломы. Для взломов должно выполняться дополнительное ограничение t ≤ 5.

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

Для каждого теста выведите одно целое число — минимальное количество попыток, которое вам придется сделать, чтобы ваша доля успешных попыток стала равна вашему любимому рациональному числу, либо -1, если добиться желаемого невозможно.

Пример
Входные данные
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
Выходные данные
4
10
0
-1
Примечание

В первом тесте необходимо сделать 4 успешные попытки. Тогда ваша доля успешных попыток составит 7 / 14, или 1 / 2.

Во втором тесте нужно совершить 2 успешные и 8 безуспешных попыток. Тогда ваша доля успешных попыток составит 9 / 24, или 3 / 8.

В третьем тесте нет надобности отсылать решения на проверку, ваша доля успешных попыток уже составляет 20 / 70, или 2 / 7.

В четвертом тесте единственная неудачная попытка рушит все ваши надежды иметь долю успешных попыток, равную 1.