该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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\) 盒子，在那里它将被捕捉。