Hàm Totient hay hàm phi (\(\phi\)) được định nghĩa là số lượng số tự nhiên 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\).

Input

• 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)\).

Output

• 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.

Example