Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Дробь \({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 |