题目描述

输入一个正整数 $n$，输出欧拉函数 $\varphi(n)$ 的值。$\varphi(n)$ 表示 $1 \sim n$ 中与 $n$ 互质（最大公约数为 $1$）的整数的个数。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个整数，表示 $\varphi(n)$。

样例

6

2

12

4

说明/提示

由唯一分解定理 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，有

$$\varphi(n) = n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right)$$

只需用试除法把 $n$ 质因数分解，每遇到一个不同的质因子 $p$，就令 $\varphi(n) \gets \varphi(n) / p \times (p-1)$。