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

Input:
3
2
4
7

Output:
1
1
2

Constraints

1 ≤ T ≤ 100000
2 ≤ n ≤ 10000000


Added by:Varun Jalan
Date:2010-01-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:own problem used for Codechef Snackdown Onsite

hide comments
2017-07-03 09:44:52
Precomputation makes it a cakewalk!!
2017-05-12 11:19:05 Shubham Jadhav
I am using regular sieve, with binary search, but still getting TLE Also using scanf and printf. Any idea why?
2016-10-11 08:47:51 gautam
nice one...!!
2016-08-23 20:01:07
learnt a lot after 3 hours..3 solution...but 1 accepted...finally
2016-07-21 20:53:37
Similar question ALICESIE
2016-07-07 17:15:58
i am using a similar approach as in "prime genenrator" whats wrong?
2016-07-05 19:33:45 vaibhav goyal
why fastScan with cin and cout is not working??
use scanf and printf to get AC!!
2016-07-04 15:59:50 Dilpreet
Good One..!
Think Simple.
2016-06-25 00:29:04 Piyush Kumar
Is there something wrong with the input files? Fast IO is giving TLE!

=(Francky)=> Which fast IO do you use ? Some methods can give TLE, do you know why ?

Re: I tried getchar/putchar unlocked. Given the format, it should have worked. I use fast IO only if the solution is slow, so not much expertise in that area :( .

=(Francky)=> you have to handle correctly the case where EOF comes before the last \n ; it leads to TLE !;-)

Re: O! Thanks :) !

Last edit: 2016-06-25 12:36:56
2016-06-24 14:12:02
precompute simple sieve :)
no need to optimize
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.