5341 - 数论：欧拉函数：GCD之和

给定正整数n(1 < n < 2^31)，计算∑gcd(i, n) 1<=i <=n。

Input

多组数据，每组数据的格式为： 第1行：1个整数n

Output

对每个数据，在1行：1个整数，表示如题所求的结果

Examples

Input

6

Output

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