English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/etf

Trong số học, hàm Ơ-le 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 (1 <= n <= 10^6). Tính giá trị của hàm Ơ-le .

Input

Dòng đầu chứa số nguyên T là số test (T <= 20000)

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.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
4

---

hide comments

	sssdhnam: 2023-09-16 15:13:14 hope I could AC it in 10 times ☺
	berlin03spoj: 2023-07-11 12:50:04 hic AC in 5 times :((
	shakur01: 2022-09-09 13:05:38 AC in the first go.
	ishraaq_56789: 2021-05-20 10:58:36 Proud to write an Euler Totient function from scratch and get an AC in the first go.