For a fixed positive integer n, compute the total S(n) = gcd(1, n) + gcd(2, n) + ... + gcd(n, n). This total can be evaluated efficiently using the identity S(n) = sum over divisors d of n of d * phi(n / d), where phi is Euler's totient function, but any correct method is accepted.
Input format
A single line with one integer n.
Output format
A single integer: the value of S(n).
Constraints
- 1 <= n <= 1000000000000