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
leokery: 2017-11-01 14:44:13

A naive algorithm

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.


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