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