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