Time Limit: 1000 MS    Memory Limit: 64000 K 


Description

小鱿鱼和他的显卡又闹矛盾了,小鱿鱼威胁说,你只要做出我写的题我就原谅你,那么聪明的你能不能帮显卡挽救他的小鱿鱼 给定n,计算∑gcd(i,n) (i <= n, n<10^9)。

Input

输入为多组数据 每一行是一个n

Output

每组数据,输出一行,包含一个整数n

Sample Input

3 4

Sample Output

5 8

hint

for 3, gcd (1,3) = 1,gcd(2,3) = 1,gcd(3,3), 1 + 1 + 3 = 5;