Background

One day, TIBBAR and LXL competed to see who could first compute the sum of the greatest common divisors of every pair of distinct numbers among the $n$ numbers from $1 \sim n$. LXL is still typing a complicated and lengthy program, hoping to get an answer within $100s$. TIBBAR, however, wants to pass in $1s$ for a decisive win; please help him accomplish this task.

Problem Description

Given $n$, compute

where $\gcd(i, j)$ denotes the greatest common divisor of $i$ and $j$.

Input Format

The input consists of a single line with one integer, denoting $n$.

Output Format

Output a single line with one integer representing the answer.

10

67

Hint

Constraints

• For 40% of the testdata, $n \leq 2 \times 10^3$.
• For 100% of the testdata, $2 \leq n \leq 2 \times 10^6$.

Translated by ChatGPT 5