Background

The Junior contestant zzq recently learned the Euclidean algorithm for computing the greatest common divisor (GCD).

Problem Description

By analogy with the Euclidean algorithm, zzq defined a strange 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;
}

After defining this function, zzq excitedly entered two numbers to compute the value of $f$, but found that the function fell into an infinite recursion... Therefore, zzq defines the value of $f$ to be $0$ in cases where the recursion would loop infinitely.

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

Input Format

One line containing an integer $n$.

Output Format

One line containing an integer $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$.

100

1124

2000

68204

Hint

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

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

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

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

Translated by ChatGPT 5