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