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