Sum of GCDs

Given an integer n, compute the sum

$$\sum\limits_{i=1}^{n} \gcd(i, n)$$

where $$\gcd(i, n)$$ denotes the greatest common divisor of i and n.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁶).

outputFormat

Output a single integer which is the sum of $$\gcd(i, n)$$ for all i from 1 to n.

sample

1

1