P2398 GCD SUM

Compute $$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$.

The first line contains an integer $n$.

Output a single integer on the first line representing the answer.

For 30% of the testdata, $n \leq 3000$. For 60% of the testdata, $7000 \leq n \leq 7100$. For 100% of the testdata, $n \leq 10^5$. Translated by ChatGPT 5