504052 - longge的问题

【题目描述】longge的问题(longge)

输入一个整数N,试计算∑gcd(i,N),其中(1≤i≤N)。

Input

有多组数据,每组一个整数N(1<N<2^31)。

Output

每组数据输出一行答案。

Examples

Input

2
6

Output

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