题目描述

给定正整数 $n$，求 $φ(n)$

公式解释：求 $1$ 到 $n$ 中与 $n$ 互质的个数。

输入格式

输入一个正整数 $n$

输出格式

输出一个数，表示答案

样例

8

4

数据范围

对于$100\%$的数据：$2<=n<=10^9$