Несократимые правильные дроби

Дробь вида m/n называется правильной, если 0 ≤ m < n и несократимой если gcd(m, n) = 1. Для заданного положительного целого n, в этой задаче Вы должны найти количество несократимых правильных дробей со знаменателем n.

Например, множество всех простых дробей со знаменателем 12, имеет вид:

После сокращения оно имеет такой вид:

Поэтому существует всего лишь 4 несократимых правильных дроби со знаменателем 12:

Технические условия

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

Каждая строка входного файла содержит одно едиственное целое число n (n < 2000000000) и ввод продолжается пока не встретится число 0 в качестве n (для этого значения входные данные не обрабатываются).

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

Для каждого n в выходном файле выведите в отдельной строке количество несократимых правильных дробей со знаменателем n.

Информация о задаче

Лимит времени: 3 секунды
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 22% 43/55
Классификация: Теория чисел

Пример

Пример входных данных

Пример выходных данных

4
41088
7251444

← Цепные дроби