初始时 a=1,每次按如下规则更新:
a←(a⋅k)modm要求在无限次执行更新的过程中,a 一共会取到多少个不同的值。
初始时a=1。给定两个整数k,m,系统会不断重复执行如下更新:
将 a 更新为 a←(a⋅k)mod m。
由于取模运算,a 的取值最终会进入循环。请你计算在无限次执行更新的过程中,a 一共可能取到多少个不同的值。
一行输入两个整数 k,m(0≤k≤106,1≤m≤106)。
输出一行一个整数,表示不同的 a 的个数。
输入
2 7
输出
3
输入
2 8
输出
4
输入
0 5
输出
2