НОД

По заданному значению n вычислить значение G, где

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

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

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

Входные данные

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

Выходные данные

Для каждого входного значения n вывести в отдельной строке соответствующее значение G.

Примеры