SQFREE - Square-free integers

题意翻译

求出 $1\sim n$ 中无平方因子数的个数。$T$ 组数据,$n\le10^{14}$。

题目描述

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!

输入输出格式

输入格式


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} $

输出格式


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

输入输出样例

输入样例 #1

3
1
1000
100000000000000

输出样例 #1

1
608
60792710185947