Denominator#10502
Sign in

Denominator

1 second
256 megabytes
Hard

Determine the number of proper fractions with denominators not exceeding .

A fraction \frac{a}{b} is considered proper if:

  1. and are positive integers;

  2. a \leq b;

  3. the greatest common divisor (GCD) of and is .

Input

The input consists of a single integer (1 \leq n \leq 10^6).

Output

Output a single integer representing the number of proper fractions.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  1. ( points): n \leq 10^3;

  2. ( points): n \leq 10^5;

  3. ( points): no additional constraints.