504048 - 求n的欧拉函数

【题目描述】求n的欧拉函数（Euler）

欧拉函数φ(n)，是指小于n且与n互素的正整数的个数，现输入n求其欧拉函数。

Input

有多组数据，每组数据为一个正整数n。

Output

每组数据输出n的欧拉函数值。

Examples

Input

5

Output

4
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题