e-olymp
Змагання

Euler Function

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

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

Вхідні дані

Кожний рядок є окремим тестом і містить число n (n < 109). Останній рядок містить 0 і не обробляється. Кількість тестів не більша за 100.

Вихідні дані

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

Ліміт часу 1 секунд
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
12
123456
7654321
0
Вихідні дані #1
4
41088
7251444