#描述#
DXM is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.
<BR>
<BR>
"Oh, I know, I know!" DXM shouts! But do you know? Please solve it.

#格式#
##输入格式##
Input contains several test cases each with a number N per line.

##输出格式##
For each N, output a line ∑gcd(i, N) 1&lt=i &lt=N

#样例1#
##样例输入1##

2
6

##样例输出1##

3
15

#限制#
1000ms
32768KB

#提示#

#来源#
Limitfan