e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Power + Euler function

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
12
123456
7654321
0
Çıxış verilənləri #1
4
41088
7251444