Sum of Divisors 2

Interview

Time limit0.5sMemory limit512 MB

Summary

Given N, compute the sum over all y from 1 to N of the sum of divisors of y, by counting how often each integer divides some value up to N.

Level: Medium4 of 10
Topics: Math, Number theory, Prefix sum, Brute force
Solved: No attempts yet

Problem

Given two natural numbers A and B, a natural number C that satisfies A = BC is called a divisor of A. For example, the divisors of 2 are 1 and 2, and the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. The sum of divisors of a natural number A is the total of all divisors of A, written as f(A). The sum of f(y) over all natural numbers y less than or equal to x is written as g(x).

Given a natural number N, find g(N).

Input

The first line gives the natural number N (1 ≤ N ≤ 1,000,000).

Output

Print g(N) on the first line.

Examples5

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
4
```
Example 3
Input
```
10
```
Expected output
```
87
```
Example 4
Input
```
70
```
Expected output
```
4065
```
Example 5
Input
```
10000
```
Expected output
```
82256014
```