eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Знову нескоротні

Знову нескоротні

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Дріб 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