frações irredutíveis
Problem
Uma fração \({m \over n}\) é chamada de fração irredutível própria se \(0 < ; m < n\) e \(gcd (m, n) = 1\). Encontre o número de frações irredutíveis próprias com denominador n.
Dados de entrada
A primeira linha especifica o número de denominadores para os quais encontrar o número de frações irredutíveis apropriadas N (\(N <=100\) ). Cada linha subseqüente é um número n (\(n < 10^9\)).
Impressão
Para cada n imprima a resposta para o problema em uma linha separada.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4
23
23456
7
17
|
22
11712
6
16 |