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


99% Solution Ratio

identityEarliest, Sep '19

identityFastest, 0.0s

touhidurrrLightest, 0 B

touhidurrrShortest, 79B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.