Problem 4F. Catch the ball

Description

有 $m$ 个盒子，编号从 $0$ 到 $m - 1$ 。同时有一个球放在这些盒子的其中一个里。

每秒球会从盒子 $i$ 移动到盒子 $i \cdot x\mod{m}$ 。 球的起始位置未知。

现在你可在任意盒子中放置一个捕捉器来捕捉球，当球进入这个盒子时会被立即捉住。求解所需安装的捕捉器的最小数量。

题目保证 $GCD(x, m) = 1$ 。

Input Format

唯一的一行包含两个整数 $m$ 和 $x$ ( $2 \le m \le 10^{14}$ ， $1 \le x < m$ ， $\text{GCD} (x, m) = 1$ ) - 盒子数和参数 $x$ 。

Output Format

输出唯一整数 - 捕获球所需安装的捕捉器的最小数量。

Test Case 1

input

4 3

output

3

Test Case 2

input

5 2

output

2

Note

在第一个示例中，您可以在盒子 $0$ ， $2$ ， $3$ 中放置捕捉器。如果球在其中一个房间开始，它将立即被捕捉。

如果球从 $1$ 盒子开始，那么它将移动到 $3$ 盒子，在那里它将被捕捉。