Problem
الكسر \ ({m \ over n} \) يسمى الكسر الصحيح غير القابل للاختزال إذا \ (0 & lt ؛ m & lt؛ n \) و \ (gcd (m، n) = 1 \) . أوجد عدد الكسور غير القابلة للاختزال ذات المقام n .
& nbsp؛
إدخال البيانات
يحدد السطر الأول عدد القواسم التي يتم العثور على عدد الكسور غير القابلة للاختزال المناسبة لها N ( \ (N & lt؛ = 100 \) ). كل سطر لاحق عبارة عن رقم n ( \ (n & lt؛ 10 ^ 9 \) ). & nbsp؛
نبسب ؛
بصمة
لكل n اطبع إجابة المشكلة في سطر منفصل.
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
4
23
23456
7
17
& nbsp؛
|
22
11712
6
16 |