Trong số học, hàm Euler ~\varphi~ của một số nguyên dương ~n~ được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng ~n~ và nguyên tố cùng nhau với ~n~.

Cho số nguyên dương ~n~ ~\left(1 \le n \le 10^6\right)~. Tính giá trị của hàm Euler ~\varphi~.

Input

Dòng đầu chứa số nguyên ~T~ là số test ~\left(T \le 20000\right)~.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~.

Output

~T~ dòng, mỗi dòng ghi kết quả của test tương ứng.

Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
2
4