Limits 1s, 512 MB

Prime numbers are the ones which can only be divided by 1 and the number itself. 2, 3, 5, 7, 11, 13 etc.
are prime numbers.

In this problem, you will take a number $N$ as input and print the total number of prime numbers that are in the left of $N$.

Input

In the first line of input, you will take a number $T$ ($1 \le T \le 10^5$). It indicates the total number of test cases. In the following $T$ lines, you will take a number $N$ ($1 \le N \le 10^7$) as input and print the total number of prime numbers that are in the left of $N$.

Output

For each test case print the ans of the corresponding $N$ in a newline.

Sample

InputOutput
5
1
2
3
4
5
0
0
1
2
2

Submit

Login to submit.

Statistics

70% Solution Ratio
Sajid_ZEarliest, Jun '17
emrulhasanFastest, 0.0s
codermehrajLightest, 5.1 MB
Nusab19Shortest, 251B
Toph uses cookies. By continuing you agree to our Cookie Policy.