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

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:

Дано целое число $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$.

Примеры