Fractions irréductibles
Problem
Une fraction \({m \over n}\) est appelée une fraction irréductible propre si \(0 < ; m < ; n\) et \(gcd (m, n) = 1\). Trouver le nombre de fractions irréductibles propres avec le dénominateur n.
Données d'entrée
La première ligne précise le nombre de dénominateurs pour lesquels trouver le nombre de fractions irréductibles propres N (\(N <=100\) ). Chaque ligne suivante est un nombre n (\(n < 10^9\)).
Mentions légales
Pour chaque n imprimez la réponse au problème sur une ligne séparée.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4
23
23456
7
17
22
11712
6
16 |