Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

uDebug

Left Prime
By tahmedge · 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 ≤ T ≤ 105 ). It indicates the total number of testcases. In the following T lines, you will take a number N ( 1 ≤ N ≤ 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

Input Output 
5
1
2
3
4
5
 
0
0
1
2
2

Discussion

Statistics


67% Solution Ratio

Sajid_ZEarliest, Jun '17

N_uman2962Fastest, 0.1s

likhon5Lightest, 5.6 MB

Fazlerabbi.Shortest, 298B

Submit

Login to submit

Related Contests

Intra LU Programming Contest Summer 2017 Ended at 2017-06-08 10:15:00 +0000 UTC
Replay of Intra LU Programming Contest Summer 2017 Ended at 2017-06-12 19:30:00 +0000 UTC
SUST Intra University Programming Contest 2017 (Junior) Selection 3 Ended at 2017-07-23 12:45:00 +0000 UTC