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
jawad_cs:
20161201 10:06:30
LOL...i was fooled..hehe 

aman224:
20161125 21:22:18
too easy.... 

davidgalehouse:
20161017 06:03:33
Surely if Alice is designing her own sieves then she would be able to answer this question herself. 

suvro_datta:
20160926 21:52:00
( num + 1 ) /2 

sri:
20160925 13:15:18
three if's that's it!! Simple but portrayed as hard!!!


hamjosh1:
20160915 14:18:32
pen paper :P 

smtcoder:
20160903 22:16:45
HAHAHAHA...this question is a big joke..but will make you feel like a joker if you just start making (sieve like) codes for this question without analysing it for sometime..


iit2015504:
20160807 19:34:29
PATTERN CAREFUL 

sarthak_8:
20160730 23:26:10
Better to move on to another problem as there's nothing to learn here, do it only if you want points. Observation will get you an AC. 

try2catch:
20160202 10:20:01
Accepted in 1st attempt. Feeling proud. I dedicate my success to my parents,teachers and friends. I worked hard for two months to solve these kind of problems. Never dreamt better than this.

Added by:  Paulo Costa 
Date:  20120206 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  UNI 