Given n and k, calculate $\varphi(\varphi(...\varphi(n)...))$, where $\varphi$ applied exactly k times.

$\varphi(n)$ is Euler's totient function. $\varphi(1)=1$ by definition.

You can find the definition of Euler's totient function here.

Input format

The only line of input contains two integers n and k ($1 \le n \le 10^{18}$, $1 \le k \le 10^{18}$).

Output format

Print one integer - answer to the problem.

Scoring

$n \le 10^{3}$, $k \le 10^{3}$ - 10 points

$n \le 10^{6}$, $k \le 10^{18}$ - 15 points

$n \le 10^{12}$, $k = 1$ - 10 points

$n \le 10^{12}$, $k \le 10^{18}$ - 10 points

$n \le 10^{15}$, $k = 1$ - 5 points

$n \le 10^{15}$, $k \le 10^{18}$ - 40 points

$n \le 10^{18}$, $k \le 10^{18}$ - 10 points