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\).