题目描述

请计算对于所有 $x \in \N$ 且 $x \in [2,n]$，满足 $\sqrt{x}$ 非最简二次根式的 $x$ 的个数。只要你的输出与答案的绝对误差不超过 $2\times10^4$，那么就判为 AC。

输入格式

本题多组询问。第一行输入一个数 $T$，表示询问组数。

每组询问输入一行，一个正整数 $n$。

输出格式

对于每组询问，输出一行一个整数，表示对于所有 $x \in \N$ 且 $x \in [2,n]$，满足 $\sqrt{x}$ 非最简二次根式的 $x$ 的个数。

3
10
32678
9686985

3
12814
3797988

提示

样例解释

对于所有 $x \in \N$ 且 $x \in [2,10]$，只有 $x=4$ （$\sqrt{4}=2$）、$x=8$ （$\sqrt{8}=2\sqrt{2}$）和 $x=9$ （$\sqrt{9}=3$）非最简二次根式，因此 $n=10$ 时输出 $3$。

需要注意的是，由于你的答案被允许与标准答案有 $2\times 10^4$ 的绝对误差，因此 $-2,3,20003$ 等输出都将被认为是正确的。

数据范围

• $\text{Subtask 1(10 pts)}$：$n\le 10^5$。
• $\text{Subtask 2(20 pts)}$：$n\le 10^7$。
• $\text{Subtask 3(20 pts)}$：$n\le 10^9$。
• $\text{Subtask 4(20 pts)}$：$T=1$。
• $\text{Subtask 5(30 pts)}$：无特殊性质。

对于 $100\%$ 数据，满足 $1\le n\le 10^{18}$，$1\le T\le 10^4$，保证 $n$ 在范围内随机得到。