CF1027G.X-mouse in the Campus

The campus has $m$ rooms numbered from $0$ to $m - 1$. Also the $x$-mouse lives in the campus. The $x$-mouse is not just a mouse: each second $x$-mouse moves from room $i$ to the room $i \cdot x \mod{m}$ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $x$-mouse is unknown.

You are responsible to catch the $x$-mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $x$-mouse enters a trapped room, it immediately gets caught.

And the only observation you made is $\text{GCD} (x, m) = 1$.

校园中有 $m$ 个房间，编号从 $0$ 到 $m - 1$。此外，一只 $x$-鼠生活在校园中。这只 $x$-鼠并非普通老鼠：每秒，它会从房间 $i$ 移动到房间 $i \cdot x \mod{m}$（实际上，它通过瞬移在房间之间移动，不经过任何中间房间）。$x$-鼠的初始位置未知。

你负责在校园中捕获这只 $x$-鼠，因此你需要估计所需放置的陷阱（每个房间最多放一个陷阱）的最小可能数量。你确信：一旦 $x$-鼠进入一个布置了陷阱的房间，它将立即被捕获。

你唯一掌握的信息是 $\text{GCD} (x, m) = 1$。

The only line contains two integers $m$ and $x$ ($2 \le m \le 10^{14}$, $1 \le x \lt m$, $\text{GCD} (x, m) = 1$) — the number of rooms and the parameter of $x$-mouse.

唯一一行包含两个整数 $m$ 和 $x$（$2 \le m \le 10^{14}$，$1 \le x \lt m$，$\text{GCD} (x, m) = 1$）——分别为房间数量和 $x$-老鼠的参数。

Print the only integer — minimum number of traps you need to install to catch the $x$-mouse.

输出唯一的整数——为捕获 $x$-鼠所需的最少陷阱数量。

In the first example you can, for example, put traps in rooms $0$, $2$, $3$. If the $x$-mouse starts in one of this rooms it will be caught immediately. If $x$-mouse starts in the $1$-st rooms then it will move to the room $3$, where it will be caught.

In the second example you can put one trap in room $0$ and one trap in any other room since $x$-mouse will visit all rooms $1..m-1$ if it will start in any of these rooms.

在第一个例子中，例如，你可以在房间 $0$、$2$、$3$ 中放置陷阱。如果 $x$-mouse 从这些房间中的任意一个出发，则它将立即被捕获。如果 $x$-mouse 从第 $1$ 个房间出发，则它将移动到房间 $3$，并在那里被捕获。

在第二个例子中，你可以在房间 $0$ 中放置一个陷阱，并在其余任意一个房间中再放置一个陷阱，因为若 $x$-mouse 从房间 $1..m-1$ 中的任意一个出发，它将访问所有这些房间。