题目描述
For given integer n, count the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n.
Input
n
An integer n (1 ≤ n ≤ 1000000000).
Output
The number of totatives in a line.
Examples
Input
6
Output
2
Input
1000000
Output
400000
输入格式
见题面
输出格式
见题面
样例输入
1000000
样例输出
400000