505038 - 公约数的和

【题目描述】公约数的和(gcdsum)

给定n,求∑(i=1)^n▒∑(j=i+1)^n▒〖gcd⁡(i,j)〗,其中gcd(i,j)表示i和j的最大公约数。

Input

输入一个整数n(2≤n≤2×10^6)。

Output

输出一个整数表示答案。

Examples

Input

9

Output

50
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题