Migrated from Lutece 618 无平方因子数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

无平方因子数即对于任意一个素数$p$，$p^2$都不会整除那个数，如$1$ , $5=5$ , $15=3\times 5$都是无平方因子数，而$20=2^2\times 5$不是。现在给定一个$n$ ($1 \leq n < 10^{12}$) ，求区间$[1,n]$中无平方因子数的个数。

Input

第一行有个整数$T$，代表数据组数（$T \leq 10$）

接下来有$T$行，每行有个整数$n$ ($1 \leq n < 10^{12}$)

Output

输出$T$行，每行输出一个整数代表区间$[1,n]$内的无平方因子数的个数。

Samples

3
1
10
30

1
7
19

Resources

UESTC Training for Math