G. X-мышь в общежитии
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Общежитие состоит из $$$m$$$ комнат, пронумерованных от $$$0$$$ до $$$m - 1$$$. Также в общежитии проживает $$$x$$$-мышь. $$$x$$$-мышь — это необычная мышь, так как $$$x$$$-мышь движется каждую секунду из комнаты $$$i$$$ в комнату $$$i \cdot x \mod{m}$$$ (фактически, телепортируется, так как не посещает никаких других комнат по дороге). Начальная позиция $$$x$$$-мыши неизвестна.

На Вас возложили ответственность поймать эту необычную $$$x$$$-мышь, поэтому сейчас Вам интересно, какое минимальное количество ловушек Вы должны установить (одна ловушка в одной комнате), чтобы гарантированно ее поймать. Вы можете быть уверены, что если $$$x$$$-мышь посетит комнату с установленной в ней ловушкой, то она абсолютно точно будет поймана.

Единственное сделанное Вами наблюдение: $$$\text{GCD} (x, m) = 1$$$.

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

Единственная строка содержит 2 целых числа $$$m$$$ и $$$x$$$ ($$$2 \le m \le 10^{14}$$$, $$$1 \le x < m$$$, $$$\text{GCD} (x, m) = 1$$$) — количество комнат и параметр $$$x$$$-мыши.

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

Выведите единственное число — минимальное количество ловушек, которое Вам надо установить, чтобы гарантированно поймать $$$x$$$-мышь.

Примеры
Входные данные
4 3
Выходные данные
3
Входные данные
5 2
Выходные данные
2
Примечание

В первом примере вы можете, например, установить ловушки в комнатах $$$0$$$, $$$2$$$, $$$3$$$. Если $$$x$$$-мышь начнет в одной из этих комнат, то она сразу будет поймана. Если же $$$x$$$-мышь начнет путешествие в $$$1$$$-й комнате, то она будет поймана, когда переместится в комнату $$$3$$$.

Во втором примере мы можете поставить одну ловушку в комнату $$$0$$$ и одну ловушку в любую другую комнату, так как если $$$x$$$-мышь начнет двигаться из любой комнаты в диапазоне $$$1..m-1$$$ она посетит все комнаты из данного диапазона.