题目内容

小蓝定义了一个数列生成规则：给定一个乘数 $p$ 和一个上限 $q$，从 $x = 1$ 开始，反复将 $x$ 更新为 $(x \times p) \bmod q$。由于可能的取值有限，这个过程最终会进入循环。请你计算在无限次操作中，一共会产生多少个不同的 $x$ 值。

约束：$p$ 的范围是 $0 \le p \le 10^6$，$q$ 的范围是 $1 \le q \le 10^6$。

输入描述

输入包含一行，包含两个整数 $p$ 和 $q$（$0 \le p \le 10^6$，$1 \le q \le 10^6$），分别表示乘数和上限。

输出描述

输出一个整数，表示能得到的不同的 $x$ 值的个数。

样例1

输入

3 10

输出

4

说明

从 $x=1$ 开始，按规则依次计算：$1 \rightarrow 3 \rightarrow 9 \rightarrow 7 \rightarrow 1$。 得到的不同值有 1、3、9、7，后续不再产生新值，因此总共有 4 个不同值。

样例2

输入

0 5

输出

2

说明

当 $p=0$ 时，对任意 $x$ 都有 $(x \times 0) \bmod q = 0$。 从 1 开始，第一次更新得到 0，之后永远停留在 0。 因此产生的不同值只有 1 和 0，共 2 个。

样例3

输入

6 9

输出

3

说明

序列更新过程：$1 \times 6 \bmod 9 = 6$，$6 \times 6 \bmod 9 = 0$，$0 \times 6 \bmod 9 = 0$。 依次出现的值为 1、6、0，之后不再产生新值，不同值总数为 3。