Irreducible fractions
Problem
A fraction \({m \over n}\) is called a proper irreducible fraction if \(0 < m < ; n\) and \(gcd (m, n) = 1\). Find the number of proper irreducible fractions with denominator n.
Input data
The first line specifies the number of denominators for which to find the number of proper irreducible fractions N (\(N <=100\)). Each subsequent line is a number n (\(n < 10^9\)).
Imprint
For each n print the answer to the problem in a separate line.
Examples
| # |
Input |
Output |
| 1 |
4
23
23456
7
17
|
22
11712
6
16 |