题目描述

Longge 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<231),you are to calculate ∑gcd(i,N)
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

输入格式

Input contain several test case.
A number N per line.

输出格式

For each N, output ,∑gcd(i,N) 1≤i≤N, a line

样例

2
6

3
15