\(\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 FORMAT

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 FORMAT

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

Ví dụ 1:

Input

5
1
2
3
4
5

Ouput

1
1
2
2
4

Giải thích ví dụ mẫu:

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.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House