Cho số nguyên dương \(n\).

Yêu cầu: Đếm số lượng các số nguyên tố trong phạm vi từ 0 đến \(n\).

Input

• Dòng đầu tiên chứa số nguyên \(T (1≤T≤10^4)\) là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n(0≤n≤10^6 ).\)

Output

• Gồm \(T\) dòng, mỗi dòng ghi số lượng các số nguyên tố trong phạm vị từ 0 đến \(n\) ứng với test tương ứng.

Sample Input

2
6
39

Sample Output

3
12