Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла: Дано целое число $n$. Вычислите $∑gcd(i, n)$ для всех $1 \le i \le n$. "\textit{О, я знаю, я знаю!}" - воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её. \InputFile Каждая строка содержит одно число $n~(1 < n < 2^{31})$. \OutputFile Для каждого значения $n$ выведите в отдельной строке сумму $∑gcd(i, n)$ для всех $1 \le i \le n$.