Cho số nguyên dương \(N\). Tính tổng: \(S = \sum_{i=1}^{N} \sum_{j=1}^{N} \gcd(i, j)\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(N\) (\(1 \le N \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là \(S\).

Ví dụ

Input:

4

Output:

20

Giải thích: Các cặp gcd: \((1, 1) = 1,\)(1, 2) = 1,\((1, 3) = 1,\)(1, 4) = 1,\((2, 1) = 1,\)(2, 2) = 2,\((2, 3) = 1,\)(2, 4) = 2,\((3, 1) = 1,\)(3, 2) = 1,\((3, 3) = 3,\)(3, 4) = 1,\((4, 1) = 1,\)(4, 2) = 2,\((4, 3) = 1,\)(4, 4) = 4. Tổng = 20.

Ràng buộc

• 100% số điểm: \(N \le 10^{6}\).