Irreducible Basic Fractions

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

A fraction is called basic, when m / n s.t. 0<=m<n; A fraction is called irreducible, when gcd(m, n)=1;
Now given a number n, and you are to find out the number of fractions (basic irreducible fractions) with the denominator of n.
 

Input

Multiple input cases, and each with a single number n.
 

Output

The answer.

Sample Input

12

Sample Output

4

Hint

0/12, 1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12.
=>
1/12, 5/12, 7/12, 11/12
=>4

Source

zhengnanlee