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


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

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

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

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

Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем \(n\).
 
Входные данные: В первой строке задается число знаменателей для которых надо найти количество правильных несокртимых дробей N (N <=100). Каждая последующая строка число n (n < 109). 
Выходные данные: Для каждого n в отдельной строке вывести ответ на поставленную задачу.
Примеры:
Входные данные Выходные данные
1
4
23
23456
7
17
 
22
11712
6
16