Practice on Toph

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

Relatively Prime

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 < 1000).

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


100% Solution Ratio

identityEarliest, 10M ago

identityFastest, 0.0s

touhidurLightest, 0 B

touhidurShortest, 79B

Submit

Login to submit