FINDPRM  Finding Primes
One commonly used method to calculate all primes in the range [2..n] is to start with the number 2, mark it as prime, and mark all its multiples (excluding itself) as not prime. Then, we find the next smallest unmarked number, mark it as prime, and mark all its multiples (excluding itself) as not prime. Continuing this way, we get a list of all primes.
Now, let us say that we modified the above algorithm, and start with n instead of 2. We mark it as prime, and mark all its factors (excluding itself) as not prime. Then we find the next greatest unmarked number, mark it as prime, and mark all its factors (excluding itself) as not prime. Continuing this way, we get a list of all primes.
Now you wonder, given a value of n, how many numbers are such that both the above algorithms will mark them as prime?
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required answer.
Example
Sample Input :
3
2
4
7
Sample Output :
1
1
2
Constraints
1 <= T <= 100000
2 <= n <= 10000000
hide comments
aayush_b1999:
20190717 18:23:30
if you get tle with sieve and precomputation then use printf (for c++) 

vbv_2312:
20190204 19:17:16
very good question....youll get to know many things if you try to get an AC in the given time limit.......must do question


dream_kid:
20180412 12:51:29
my 50th :) 

kuchnahiaata:
20180321 15:55:38
learned the beauty of precomputation from this problem 

venky1001:
20180206 16:51:17
same code TLE in JAVA, Accepted in C++ 

itachi_2016:
20171229 07:48:13
Easy question. Just simple sieve and some minor modification to find out number of primes :) Last edit: 20171229 07:51:05 

pvsmpraveen:
20170810 09:59:19
Needs Fast I/O ... Maybe its better if its mentioned as LARGE I/O 

hassanarif63:
20170703 09:44:52
Precomputation makes it a cakewalk!! 

Shubham Jadhav:
20170512 11:19:05
I am using regular sieve, with binary search, but still getting TLE Also using scanf and printf. Any idea why? 

gautam:
20161011 08:47:51
nice one...!! 
Added by:  Varun Jalan 
Date:  20100124 
Time limit:  0.254s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 
Resource:  own problem used for Codechef Snackdown Onsite 