Phi hàm euler

Trong một vũ trụ song song, tồn tại một hành tinh kỳ lạ nơi mà sự hài hòa của vạn vật được đo lường bằng một hàm số toán học cổ đại, được gọi là hàm Euler \((\varphi)\). Hàm \(\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 nhỏ hơn hoặc bằng \(n\) và nguyên tố cùng nhau với \(n\).

Tuy nhiên, việc tính toán giá trị này cho các số lớn là một thách thức lớn. Các nhà toán học của hành tinh đang cố gắng tìm ra một phương pháp hiệu quả để giải quyết vấn đề này, vì nó sẽ giúp họ hiểu rõ hơn về sự hài hòa của vũ trụ.

Bạn là một nhà toán học trẻ tuổi, được giao nhiệm vụ xây dựng một chương trình để tính giá trị của hàm Euler \(\varphi\) cho một số lượng lớn các số nguyên dương.

Yêu cầu:
Cho số nguyên dương \(n\) (\(1 \le n \le 10^6\)). Hãy tính giá trị của hàm Euler \(\varphi(n)\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(T \le 20000\)), là số test.
• \(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

5
1
2
3
4
5

1
1
2
2
4

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(T, n \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.