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
2021-03-26 19:29:12
Even after using BufferedReader it doesn't work for java :( Any suggestions?
2020-12-02 16:38:51
tip use sive, precomutation from n will give amswer NO TLE
2019-11-16 18:44:45
cin cout TLE, printf scanf accept
2019-07-17 18:23:30
if you get tle with sieve and precomputation then use printf (for c++)
2019-02-04 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
2018-04-12 12:51:29
my 50th :)
2018-03-21 15:55:38
learned the beauty of pre-computation from this problem
2018-02-06 16:51:17
same code TLE in JAVA, Accepted in C++
2017-12-29 07:48:13
Easy question. Just simple sieve and some minor modification to find out number of primes :)

Last edit: 2017-12-29 07:51:05
2017-08-10 09:59:19
Needs Fast I/O ... Maybe its better if its mentioned as LARGE I/O
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.