SQFREE - Square-free integers

In number theory we call an integer square-free 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 ≤ 1014

Output

T lines, on each line output the number of (positive) square-free integers not larger than n.

Example

Input:
3
1
1000
100000000000000

Output:
1
608
60792710185947
Warning: A naive algorithm will probably not be sufficient to be accepted.

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

hide comments
2009-05-17 20:44:35 Gogu
don't think you can get rid of divisions. at least I can't think of any way to do this.
2009-04-06 13:39:37 [Trichromatic] XilinX
I've no idea about that.
2009-04-06 08:34:59 amaroq
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.
To prevent spoiling the problem, please only answer 'yes' or 'no'.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.