题目描述

如果一个自然数 $x$ 不存在某个自然数 $y>1$，使得 $y^2$ 能整除 $x$，那么称 $x$ 为平方自由数。

给定一个自然数 $n$，求区间 $[1,n]$ 中平方自由数的个数。

由于这个版本过于简单，你需要回答 $q$ 组这样的询问。

请编写程序 square_free，对于每组给定的 $n$，输出不大于 $n$ 的平方自由数个数。

输入格式

第一行输入一个整数 $q$，表示测试组数。

接下来 $q$ 行，每行一个整数 $n$，表示一组询问。

输出格式

输出 $q$ 行。

对于每组询问，输出一个整数，表示答案。

数据范围

• $1 \le n \le 10^{14}$
• $1 \le q \le 500$

子任务

只有通过某个子任务中的全部测试点，才能获得该子任务的全部分数。

样例输入 #1

2
4
10

样例输出 #1

3
7

样例说明 #1

不超过 $10$ 的平方自由数为：$1,2,3,5,6,7,10$。