# 公约数的和

## 题目背景

有一天，TIBBAR 和 LXL 比赛谁先算出 $1 \sim n$ 这 $n$ 个数中每任意两个不同的数的最大公约数的和。LXL 还在敲一个复杂而冗长的程序，争取能在 $100s$ 内出解。而 TIBBAR 则直接想 $1s$ 秒过而获得完胜，请你帮他完成这个任务。

## 题目描述

给定 $n$，求
$$\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)$$

其中 $\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数。

## 输入格式

输入只有一行一个整数，表示 $n$。

## 输出格式

输出一行一个整数表示答案。

## 样例 #1

### 样例输入 #1

```
10
```

### 样例输出 #1

```
67
```

## 提示

#### 数据规模与约定

- 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 2 \times 10^6$。