Phi hàm Euler

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

\(\phi(N)\) là số số nguyên tố cùng nhau với \(N\) trong đoạn từ \(1\) đến \(N\). Viết chương trình tính giá trị của \(\phi(N)\).

Input

Dòng đầu tiên nhập giá trị \(T\) là số lượng testcase \((T \leq 2\times 10^5)\)

\(T\) dòng tiếp theo nhập vào số nguyên \(N (1 \leq N \leq 10^6)\)

Output

In ra giá trị của \(\phi(N)\) tương ứng với mỗi testcase.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5
1
2
3
4
5

Output

1
1
2
2
4

Giải thích ví dụ

Ví dụ 1

• Giải thích: Tính \(\phi(1)\) là 1 vì chỉ có số 1 trong đoạn từ 1 đến 1.

Ví dụ 2

• Giải thích: Tính \(\phi(4)\) là 2 vì có hai số (1 và 3) nguyên tố cùng nhau với 4 trong đoạn từ 1 đến 4.

Thông tin học tập

• Buổi: B08
• Concepts: Euler's totient, prime factorization, preprocessing
• Giới hạn kiến thức: B01-B08
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30