# 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


### Statistics

89% Solution Ratio

identityEarliest, Sep '19

identityFastest, 0.0s

identityLightest, 0 B

bokaifShortest, 81B