Algorithms and Data Structures

Euler's totient function

For a given number n, you are asked to calculate the result of Euler’s totient function.
Euler’s totient function calculates the number of integers from 1 to n that are relatively prime to n. Meaning all the numbers with the greatest common divisor with n equal to 1.
 
The first thousand values of the totient function. Source: Wikipedia.
The first thousand values of the totient function. Source: Wikipedia.

Input

The input contains a single integer n (1 ≤ n ≤ ).

Output

The program should print the result of Euler's totient function for n.

Examples

Input
Output
20
8
9
6

Explanation

  1. 20 → 1, 3, 7, 9, 11, 13, 17, 19
  1. 9 → 1, 2, 4, 5, 7
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue