Опять несократимые

Дробь m/n называется правильной несократимой, если 0 < m < n и НОД (m, n) = 1. Найдите количество правильных несократимых дробей со знаменателем n.

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

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

Каждая строка является отдельным тестом и содержит число n (n < 10⁹). Последняя строка содержит 0 и не обрабатывается. Количество тестов не больше 100.

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

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

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

Лимит времени: 0.1 секунды
Лимит памяти: 64 MB
Баллы за пройденный тест: 4
Сложность: 20% 63/79

Пример

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

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

4
41088
7251444

← Моя любимая, несократимая…

Список задач