505005 - GCD求和

【题目描述】GCD求和（gcdsum）

给定一个整数N，你需要求出∑_(i=1)^N▒〖gcd⁡(i,N)〗。

Input

一行包含一个正整数N（1≤N≤109）。

Output

一个整数，表示答案。

Examples

Input

6

Output

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