e-olymp

НОД

По заданному значению 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