DSA Level 3 Competitive Number Theory Eulers Totient Function

Eulers Totient Function

hard

Question Solve Solutions

you have been given a number n, count the number of integers between 1 to n inclusive, which are co-prime to n.

Input Format

The first line contains the integer n.

Output Format

Output an integer in a line.

Constraints

1 &lt;= n &lt;= 10^9

Example

Input

Output

Linear Diophantine Equation

Wilsons Theorem

Related Questions

medium Extended Euclidean Algorithm medium Linear Diophantine Equation medium Wilsons Theorem medium Modular Fast Exponentiation medium Modular C(n,r) hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs medium Sum Of Factors easy Chinese Remainder Theorem easy Monkey Tradition