Frazioni irriducibili
Problem
Una frazione \({m \over n}\) è detta frazione propria irriducibile se \(0 < ; m < ; n\) e \(gcd (m, n) = 1\). Trova il numero di frazioni proprie irriducibili con denominatore n.
Inserisci dati
La prima riga specifica il numero di denominatori per cui trovare il numero di frazioni irriducibili proprie N (\(N <=100\) ). Ogni riga successiva è un numero n (\(n < 10^9\)).
Impronta
Per ogni n stampa la risposta al problema in una riga separata.
Esempi
| # |
Input |
Uscita |
| 1 |
4
23
23456
7
17
|
22
11712
6
16 |