SQFREE - Square-free integers

题意翻译

# 题目描述 在数论中,如果一个整数不能被任何一个整数(这个整数不是1)的平方整除,我们就称它是一个Square-free integer(无平方数因数的数)。你得数一数! # 输入输出格式 **输入格式:** 第一行包含一个整数T(T≤100)。以下T行每个包含一个正整数:n,其中n≤$10^{14}$。 **输出格式:** T行,在每一行上输出不大于n的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!

输入输出格式

输入格式


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