e-olymp

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

Дробь 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