Nguyên tố cùng nhau

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho số nguyên dương N. Hãy đếm số lượng số nguyên dương i không vượt quá N sao cho ~\gcd(i,N)=1~.

Trong đó, ~\gcd(a,b)~ là ước chung lớn nhất của hai số nguyên dương a và b.

Input

  • Dòng đầu tiên chứa số nguyên T là số lượng bộ test (~1 \le T \le 10~).

  • T dòng tiếp theo, mỗi dòng chứa một số nguyên N (~1 \le N \le 10^9~).

Output

  • Gồm T dòng, mỗi dòng chứa kết quả tương ứng với một bộ test.

Ví dụ

Sample Input
5
100
200
155
210
985
Sample Output
40
80
48
48
784

Phân chia điểm

  • Subtask 1 (50% số điểm): ~1 \le N \le 10^5~.

  • Subtask 2 (50% số điểm): Không có giới hạn bổ sung.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.