Hàm Totient hay hàm phi (\(\phi\)) được định nghĩa là số lượng số nguyên dương bé hơn hoặc bằng \(n\) và nguyên tố cùng nhau với \(n\). Hàm Totient của \(n\) được ký hiệu là \(\phi(n)\).

Cho số nguyên dương \(n\), hãy tính giá trị của hàm Totient tại \(n\).

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương \(T\) \((1 \le T \le 10^5)\).
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) \((1 \le n \le 10^6)\).

Dữ liệu ra

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên là giá trị của hàm Totient tại \(n\) tương ứng.

Ví dụ