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 probably not works.

hide comments
xiaoyimi: 2017-01-05 03:53:18

It's so crazy!
I don't think this problem can be accepted by O(T√n)!

cccsober: 2016-06-26 13:11:40

mobius is enough...

Scape: 2015-09-21 15:53:07

nlogn is sufficient to get Accepted.

Who: 2014-11-25 11:58:35

Finally AC :), nice problem i had to improve my mu function in nloglogn

:D: 2012-08-31 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.

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.

Raghavendran Ramachandran: 2012-08-31 05:13:53

The source limit is too strict. Even a solution of size 1946 bytes was rejected.

(Tjandra Satria Gunawan)(曾毅昆): 2012-07-30 08:41:46

Finally I got AC. Need a lot of optimizations to solve this problem.

Gogu: 2009-05-17 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: 2009-04-06 13:39:37

I've no idea about that.

amaroq: 2009-04-06 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.
To prevent spoiling the problem, please only answer 'yes' or 'no'.


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