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 probably not works.
hide comments
xiaoyimi:
20170105 03:53:18
It's so crazy!


cccsober:
20160626 13:11:40
mobius is enough... 

Scape:
20150921 15:53:07
nlogn is sufficient to get Accepted. 

Who:
20141125 11:58:35
Finally AC :), nice problem i had to improve my mu function in nloglogn 

:D:
20120831 06:19:12
The limit is sensible since a lot of users passed it and it's a setters decision to make it strict. And are you sure you had 1946B, not 1,9KB for example? From what I checked it works fine.


Raghavendran Ramachandran:
20120831 05:13:53
The source limit is too strict. Even a solution of size 1946 bytes was rejected. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120730 08:41:46
Finally I got AC. Need a lot of optimizations to solve this problem. 

Gogu:
20090517 20:44:35
don't think you can get rid of divisions. at least I can't think of any way to do this. 

[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 JS 
Resource:  classic, own input 