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 ≤ T ≤ 10).
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N (1 ≤ N ≤ 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 ≤ N ≤ 10^5.
• Subtast 2 (50 \% số điểm): Không có giới hạn gì thêm.