Криптограф работает с простой схемой шифрования, где для расшифровки нужно подобрать обратный ключ.

Известны два целых числа a и m. Требуется найти такое целое число x из диапазона [1, m - 1], что применение ключа x обращает действие ключа a, то есть выполняется условие:

a * x ≡ 1 (mod m)

Если подходящего обратного ключа не существует, выведите -1.

Известно, что обратный ключ к a по модулю m существует тогда и только тогда, когда gcd(a, m) = 1. В этом случае в диапазоне [1, m - 1] он единственен.

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

В единственной строке через пробел заданы два целых числа a и m.

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

Выведите одно целое число — обратный ключ x к a по модулю m из диапазона [1, m - 1], либо -1, если он не существует.

Ограничения

• 1 <= a < m
• 2 <= m <= 10^9

Примеры

Пример 1

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

1 2

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

1

Пример 2

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

4 10

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

-1