Background

pj Group contestant zzq recently learned the Euclidean algorithm for finding the greatest common divisor.

Problem Description

Analogizing to the Euclidean algorithm, zzq defined a peculiar function:

typedef long long ll;
ll f(ll a, ll b)
{
    if (a == b) return 0;
    if (a > b) return f(a - b, b + b) + 1;
    else return f(a + a, b - a) + 1;
}

Excited after defining this function, zzq randomly input two numbers to calculate the value of f, only to find that the function entered an infinite loop... Therefore, zzq defined the value of f as 0 in cases where the function recurses indefinitely.

Now, zzq inputs a number n and wants to calculate $\sum_{i=1}^n \sum_{j=1}^n f(i, j)$.

Input Format

A single line containing a number n.

Output Format

A single line containing the value of $\sum_{i=1}^n \sum_{j=1}^n f(i, j)$.

Sample Input and Output

Sample Input #1

100

Sample Output #1

1124

Sample Input #2

2000

Sample Output #2

68204

Notes

For 10% of the data, $n \leq 300$.

For 40% of the data, $n \leq 2000$.

For 70% of the data, $n \leq 5 \times 10^5$.

For 100% of the data, $1 \leq n \leq 5 \times 10^{11}$.

见题面 Input 部分

见题面 Output 部分