e-olymp
Змагання

Euler Function

НСД

За заданим значенням n обчислити значення G, де

prb1146.gif

Через GCD(i, j) позначено найбільший спільний дільник цілих чисел i та j.

Для тих, хто не зустрічався зі знаком суми пояснюємо, що значення G формально по наведеній формулі обчислюється за допомогою коду:

prb1146_1.gif

Тут GCD() позначає функцію знаходження найбільшого спільного дільника двох чисел.

Вхідні дані

Складається не більше ніж зі 100 рядків. Кожний рядок містить єдине натуральне число n (1 < n < 501). Останній рядок містить n = 0 і не обробляється.

Вихідні дані

Для кожного вхідного значення n вивести в окремому рядку відповідне значення G.

Ліміт часу 1 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
10
100
500
0
Вихідні дані #1
67
13015
442011