Вы — опытный участник соревнований Codeforces. Недавно вы обнаружили, что за все время своего участия в раундах Codeforces успели сделать y попыток, из которых x были успешными. Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x / y.
Ваше любимое рациональное число в диапазоне [0;1] — это p / q. Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать свою долю успешных попыток равной p / q?
Выходные данные
Для каждого теста выведите одно целое число — минимальное количество попыток, которое вам придется сделать, чтобы ваша доля успешных попыток стала равна вашему любимому рациональному числу, либо -1, если добиться желаемого невозможно.
Примечание
В первом тесте необходимо сделать 4 успешные попытки. Тогда ваша доля успешных попыток составит 7 / 14, или 1 / 2.
Во втором тесте нужно совершить 2 успешные и 8 безуспешных попыток. Тогда ваша доля успешных попыток составит 9 / 24, или 3 / 8.
В третьем тесте нет надобности отсылать решения на проверку, ваша доля успешных попыток уже составляет 20 / 70, или 2 / 7.
В четвертом тесте единственная неудачная попытка рушит все ваши надежды иметь долю успешных попыток, равную 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
|
4
10
0
-1
|