Big Sum

Time limit2sMemory limit1024 MB

Summary

Given n up to 10^12, compute the sum over each divisor d of n of gcd(d, i) summed for i from 1 to n.

Level: Medium6 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

Kolya learned about divisibility and greatest common divisors in math class. The greatest common divisor of two positive integers a and b, written $g = \gcd(a, b)$ , is the largest positive integer g that divides both a and b.

His teacher gave him a homework problem: for a number k, compute $\sum_{i=1}^{k}\gcd(k, i)$ . Kolya generalized it. For each divisor d of n, he sums gcd(d, i) for i up to n instead of up to d, giving $\sum_{d|n}\sum_{i=1}^{n}\gcd(d, i)$ . Here $d|n$ means that d is a divisor of n.

For large n, computing this expression directly takes a long time. Write a program that computes the value of this expression for a given n.

Input

The input file contains one positive integer n ( $1 \le n \le 10^{12}$ ).

Output

Print one number, the value of the expression for the given n.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
4
```
Expected output
```
18
```