Общежитие состоит из \(m\) комнат, пронумерованных от \(0\) до \(m - 1\). Также в общежитии проживает \(x\)-мышь. \(x\)-мышь — это необычная мышь, так как \(x\)-мышь движется каждую секунду из комнаты \(i\) в комнату \(i \cdot x \mod{m}\) (фактически, телепортируется, так как не посещает никаких других комнат по дороге). Начальная позиция \(x\)-мыши неизвестна.
На Вас возложили ответственность поймать эту необычную \(x\)-мышь, поэтому сейчас Вам интересно, какое минимальное количество ловушек Вы должны установить (одна ловушка в одной комнате), чтобы гарантированно ее поймать. Вы можете быть уверены, что если \(x\)-мышь посетит комнату с установленной в ней ловушкой, то она абсолютно точно будет поймана.
Единственное сделанное Вами наблюдение: \(\text{GCD} (x, m) = 1\).
Выходные данные
Выведите единственное число — минимальное количество ловушек, которое Вам надо установить, чтобы гарантированно поймать \(x\)-мышь.
Примечание
В первом примере вы можете, например, установить ловушки в комнатах \(0\), \(2\), \(3\). Если \(x\)-мышь начнет в одной из этих комнат, то она сразу будет поймана. Если же \(x\)-мышь начнет путешествие в \(1\)-й комнате, то она будет поймана, когда переместится в комнату \(3\).
Во втором примере мы можете поставить одну ловушку в комнату \(0\) и одну ловушку в любую другую комнату, так как если \(x\)-мышь начнет двигаться из любой комнаты в диапазоне \(1..m-1\) она посетит все комнаты из данного диапазона.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
|
3
|
|
2
|
5 2
|
2
|