Trong số học, phi hàm Euler ~\varphi(n)~ 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 không vượt quá ~n~ và nguyên tố cùng nhau với ~n~ (nghĩa là có ước chung lớn nhất với ~n~ bằng ~1~).

Per phải tính ~\varphi(n)~ cho rất nhiều giá trị ~n~ khác nhau. Các bạn học viên hãy giúp Per nhé!

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~T~ — số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~.

Kết quả

In ra ~T~ dòng, dòng thứ ~i~ là giá trị ~\varphi(n)~ của bộ test thứ ~i~.

Ví dụ

Đầu vào:

5
1
2
3
4
5

Đầu ra:

1
1
2
2
4

Giải thích: Với ~n = 4~, các số không vượt quá ~4~ và nguyên tố cùng nhau với ~4~ là ~1~ và ~3~, nên ~\varphi(4) = 2~. Với ~n = 5~ thì cả ~1, 2, 3, 4~ đều nguyên tố cùng nhau với ~5~, nên ~\varphi(5) = 4~. Theo quy ước, ~\varphi(1) = 1~.

Giới hạn

• ~1 \le T \le 20000~
• ~1 \le n \le 10^6~