ALICESIE  Alice Sieve
Alice has recently learned to use the Sieve of Eratosthenes, an ancient algorithm for finding all prime numbers up to any given limit. As expected, she was really impressed by it's simplicity and elegancy.
Now, she has decided to design her own sieve method: The Sieve of Alice, formally defined by the following procedure, which determines the Sieve of Alice up to a given limit N.
 Create a list of consecutive integers from N to 2 (N, N1, N2, ..., 3, 2). All of those N1numbers are initially unmarked.
 Initially, let P equal N, and leave this number unmarked.
 Mark all the proper divisors of P (i.e. P remains unmarked).
 Find the largest unmarked number from 2 to P – 1, and now let P equal this number.
 If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.
Unfortunately, Alice has not found an useful application for it's Sieve. But she still wants to know, for a given limit N, how many integers will remain unmarked.
Input
The first line contains an integer T, the number of test cases (1 ≤ T ≤ 10^4) . Each of the next T lines contains an integer N (2 ≤ N ≤ 10^6).
Output
Output T lines, one for each test case, containing the required answer.
Example
Input: 3 2 3 5 Output: 1 2 3
hide comments
rv111:
20180216 08:14:48
took this question in wrong way and successfully wasted my couple of hours..., 

sanyam19:
20180102 07:45:57
easy peasy... :) 

mpride44:
20171228 17:24:42
hahaha....never expect this type of ques on spoj... 

aronzx:
20170828 07:10:38
You need to observe a pattern to solve this. My 100 problem :D 

nadstratosfer:
20170820 15:05:29
Last edit: 20170820 15:08:30 

Arka Roy:
20170818 11:28:46
that feeling when you get the logic of a good question and question like this fools you !! :p this question is a reminder to think simple 

hunnychauhan:
20170718 13:59:45
just observe the pattern...


hassanarif63:
20170703 07:47:58
cakewalk! 

kooljais24:
20170619 17:19:27
lt's too much easy..O(1)...just observe the results


jainsahil1997:
20170519 07:11:48
Fooled here :P 
Added by:  Paulo Costa 
Date:  20120206 
Time limit:  0.310s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  UNI 