Unbeschränkbare Brüche
Problem
Der
Bruch von \({m \over n}\) wird als korrekt nicht reduzierbar bezeichnet, wenn \(0 < m < n\) und \(KNOTEN (m, n) = 1\). Finde die Anzahl der korrekten, nicht reduzierbaren Brüche mit dem Nenner n.
Eingaben
Die erste Zeile gibt die Anzahl der Nenner an, für die die Anzahl der korrekten, nicht reduzierbaren Brüche gefunden werden muss N (\(N <=100\)). Jede nachfolgende Zeile ist eine Zahl n (\(n < 10^9\)).
Ausgabe
Geben Sie für jedes n in einer separaten Zeile die Antwort auf die Aufgabe aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
4
23
23456
7
17
|
22
11712
6
16 |