Denominator

Determine the number of proper fractions with denominators not exceeding $n$.

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

1. $a$ and $b$ are positive integers;

2. $a\le b$;

3. the greatest common divisor (GCD) of $a$ and $b$ is $1$.

Input

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

Output

Output a single integer representing the number of proper fractions.

Examples

Scoring

1. ($30$ points): $n\le 10^3$;

2. ($40$ points): $n\le 10^5$;

3. ($30$ points): no additional constraints.