GCD Escape

問題文

正整数 $K,M$ が与えられる。

変数 $x$ があり、はじめ、 $x = KM$ である。

次の操作を好きな回数行えるとき、操作を行うことのできる回数の最大値を求めよ。

• $y \lt x$ と $\gcd(x,M) \neq \gcd(y,M)$ の両方を満たす非負整数 $y$ を選び、変数 $x$ を $y$ に変更する。

制約

• 入力はすべて整数である。
• $1 \le K, M \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル 1

入力

2 15

出力

24