Badly implemented sieve of Eratosthenes

Count how many times the inner statement runs in a nested loop where the outer index i goes from 1 to n and the inner step is i, for n up to 10^9.

Easy3MathNumber theoryImplementationNo attempts yetTime limit1sMemory limit512 MB

Problem

Seongwon implemented the sieve of Eratosthenes in C++ from memory after class. Hyeongseok, sitting next to him, said the code was wrong, and the two decided to count how many times line 6 runs. Given nn, compute that count.

The code is as follows.

int n;
cin >> n; // read n
int* sieve = new int[n + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        sieve[j] += 1; // line 6
    }
}

The outer loop runs ii from 11 to nn. The inner loop starts jj at 11 and adds ii while jj does not exceed nn. Line 6 is the body of the inner loop, and the task is its total execution count.

Input

The first line contains a natural number nn with 1n1091 \le n \le 10^9.

Output

Print the total number of executions of line 6 on the first line.