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

Задача 31849. Несократимые дроби


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

 

Примеры
Входные данные Выходные данные
1
4
23
23456
7
17
 
22
11712
6
16