Cho một số nguyên N, hãy đếm có bao nhiêu số nguyên dương i không vượt quá N sao cho GCD(i, N) = 1.

Lưu ý: GCD(a, b) = c với c là số nguyên dương lớn nhất mà a và b đều chia hết cho c

• Dòng đầu tiên chứa 1 số nguyên T là số lượng test (1 \leq T \leq 10).
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N (1 \leq N \leq 10^9).

Gồm T dòng, mỗi dòng chứa kết quả bài toán ứng với mỗi test case.

• Subtask 1 (50% số điểm): 1 \leq N \leq 10^5.
• Subtast 2 (50% số điểm): Không có giới hạn gì thêm.