Задачи
Опять несократимые
Опять несократимые
Дробь $m / n$ называется правильной несократимой, если $0 < m < n$ и $НОД(m, n) = 1$. Найдите количество правильных несократимых дробей со знаменателем $n$.
\InputFile
Каждая строка является отдельным тестом и содержит число $n~(n < 10^9)$. Последняя строка содержит $0$ и не обрабатывается. Количество тестов не больше $100$.
\OutputFile
Для каждого $n$ в отдельной строке выведите ответ на поставленную задачу.
Входные данные #1
12 123456 7654321 0
Выходные данные #1
4 41088 7251444