Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Lack of Common Divisors

Limits 1s, 512 MB

Given a positive integer N, determine how many of the integers between 1 and N are co-prime with N.

Two numbers are co-prime if the only common positive factor of the two numbers is 1.

Input

The input will contain one integer N (0 < N < 10000000).

Output

Print a single integer–the number of integers between 1 and N that are co-prime with N.

Samples

InputOutput
15
8
InputOutput
20
8

Discussion

Statistics


92% Solution Ratio

identityEarliest, 10M ago

identityFastest, 0.0s

identityLightest, 0 B

gobhir_jolShortest, 86B

Submit

Login to submit