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


hide comments
nightwolf_9197: 2016-06-24 14:08:54

century completed

visvats_141095: 2016-06-17 17:10:45

cout gives tle
and printf accepted ! -_-

yeguzi2020: 2016-01-30 11:59:17

Any one can help me understand this input?
In case n = 4, it make 4, 5, 6, 7, 9, 11,... are primes, 3 of them are really primes (5, 7, 11) then answer for this case is at least 3.
What wrong with me?

kartikay singh: 2015-06-18 20:01:04

Simple sieve :)
No need to optimise

Ashish Sareen: 2015-05-27 18:04:43

Yes you do need to optimise prime sieve. Got too many TLE's because of that

Vipul Srivastava: 2015-04-23 21:18:11

no need to optimise the prime sieve..

Fz: 2015-04-05 11:12:20

yeah.. finally got AC! the only trick->optimise your sieve!

numerix: 2011-08-23 00:33:23

@sandeep: It's correct.

sandeep pandey: 2011-08-23 00:33:23

for n=10000000 my ans:316066
this is correct or not???


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