Module: The Euler function and other problems in number theory

Problem

2
/9

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.