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.