SQFREE  Squarefree integers
In number theory we call an integer squarefree if it is not divisible by a perfect square, except 1. You have to count them!
Input
First line contains an integer T, the number of test cases (T≤100). The following T lines each contains one positive integer: n, where n ≤ 10^{14}
Output
T lines, on each line output the number of (positive) squarefree integers not larger than n.
Example
Input: 3 1 1000 100000000000000 Output: 1 608 60792710185947Warning: A naive algorithm will probably not be sufficient to be accepted.
hide comments
[Trichromatic] XilinX:
20090406 13:39:37
I've no idea about that. 

amaroq:
20090406 08:34:59
Is there a way to avoid division in the second part of the solution? Most of my code's time is spent on dividing long longs.

Added by:  Robert Gerbicz 
Date:  20090406 
Time limit:  2.177s 
Source limit:  2009B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  classic, own input 