You are given an integer N.
You have to print number of prime numbers which are less than or equal to N
Input :
First line will contain an integer 'T' (number of test cases ).
For each test case there is an integer 'N'.
output :
for each test case print required answer.
constraints :
1<=T<=100000
2<=N<=10000000