Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Несократимые дроби

Арифметические алгоритмы Функция Эйлера

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

Ввод Вывод
4
23
23456
7
17
 
22
11712
6
16