Cho số nguyên dương N, hãy đếm xem trong đoạn từ 0 tới N có bao nhiêu số nguyên tố.

Hướng dẫn:

• Bước 1 : Sàng số nguyên tố

• Bước 2: Gọi F[i] là số lượng các số nguyên tố từ 0 tới i, xây dựng mảng F[i] sau khi sàng

Đầu vào:

• Đòng 1 là số bộ test T

• T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0＜＝N＜=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
2
4
6
8
10

Output:

1
2
3
4
4