解题思路

初始时 $a=1$，每次按如下规则更新：

要求在无限次执行更新的过程中，$a$ 一共会取到多少个不同的值。

题目内容

初始时$a = 1$。给定两个整数$k, m$，系统会不断重复执行如下更新：

将 $a$ 更新为 $a ← (a · k) mod\ m$。

由于取模运算，$a$ 的取值最终会进入循环。请你计算在无限次执行更新的过程中，$a$ 一共可能取到多少个不同的值。

输入描述

一行输入两个整数 $k, m (0 ≤ k ≤ 10^6, 1 ≤ m ≤ 10^6)$。

输出描述

输出一行一个整数，表示不同的 $a$ 的个数。

样例1

输入

2 7

输出

3

样例1

输入

2 8

输出

4

样例3

输入

0 5

输出

2