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