Проблема Лонгі

Лонгі добре розбирається у математиці, він любить задумуватись над важкими математичними задачами, які можуть бути розв'язані за допомогою деяких красивих алгоритмів. І ось виникла така задачка:

Задано ціле число $n$. Обчисліть $\sum gcd(i,n)$ для всіх $1\le i\le n$.

"О, я знаю, я знаю!" — вигукнув Лонгі! А чи знаєте Ви? Будь-ласка, розв'яжіть її.

Вхідні дані

Кожний рядок містить одне число $n(1<n<2^{31})$.

Вихідні дані

Для кожного значення $n$ виведіть в окремому рядку суму $\sum gcd(i,n)$ для усіх $1\le i\le n$.

Приклади