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
2024-10-17 10:33:19
yay, solved in atmost O(T*6079290)
2019-11-17 14:40:07
O(Tsqrt(n)) passes!!
2017-11-01 14:44:13
A naive algorithm
2017-01-05 03:53:18
It's so crazy!
I don't think this problem can be accepted by O(T√n)!
2016-06-26 13:11:40
mobius is enough...
2015-09-21 15:53:07 Scape
nlogn is sufficient to get Accepted.
2014-11-25 11:58:35 Who
Finally AC :), nice problem i had to improve my mu function in nloglogn
2012-08-31 06:19:12 :D
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.

The only thing I would complain about is that it should be always mentioned in the description. Since 95% of the time there is 50000B, I don't even pay attention to it and it comes out when trying to commit.
2012-08-31 05:13:53 Raghavendran Ramachandran
The source limit is too strict. Even a solution of size 1946 bytes was rejected.
2012-07-30 08:41:46 (Tjandra Satria Gunawan)(曾毅昆)
Finally I got AC. Need a lot of optimizations to solve this problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.