CF1036F.Relatively Prime Powers

Consider some positive integer $x$. Its prime factorization will be of form $x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$

Let's call $x$ elegant if the greatest common divisor of the sequence $k_1, k_2, \dots$ is equal to $1$. For example, numbers $5 = 5^1$, $12 = 2^2 \cdot 3$, $72 = 2^3 \cdot 3^2$ are elegant and numbers $8 = 2^3$ ($GCD = 3$), $2500 = 2^2 \cdot 5^4$ ($GCD = 2$) are not.

Count the number of elegant integers from $2$ to $n$.

Each testcase contains several values of $n$, for each of them you are required to solve the problem separately.

考虑某个正整数 $x$，其质因数分解形式为 $x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$。

若序列 $k_1, k_2, \dots$ 的最大公约数（GCD）等于 $1$，则称 $x$ 是优美的（elegant）。例如，数字 $5 = 5^1$、$12 = 2^2 \cdot 3$、$72 = 2^3 \cdot 3^2$ 是优美的；而 $8 = 2^3$（GCD = $3$）、$2500 = 2^2 \cdot 5^4$（GCD = $2$）则不是优美的。

请计算区间 $[2, n]$ 中优美整数的个数。

每个测试用例包含多个 $n$ 值，对每个 $n$ 需要单独求解该问题。

The first line contains a single integer $T$ ($1 \le T \le 10^5$) — the number of values of $n$ in the testcase.

Each of the next $T$ lines contains a single integer $n_i$ ($2 \le n_i \le 10^{18}$).

第一行包含一个整数 $T$（$1 \le T \le 10^5$）—— 表示测试用例中 $n$ 的取值个数。

接下来的 $T$ 行，每行包含一个整数 $n_i$（$2 \le n_i \le 10^{18}$）。

Print $T$ lines — the $i$-th line should contain the number of elegant numbers from $2$ to $n_i$.

输出 $T$ 行——第 $i$ 行应包含从 $2$ 到 $n_i$ 的优美数的个数。

Here is the list of non-elegant numbers up to $10$:

• $4 = 2^2, GCD = 2$;
• $8 = 2^3, GCD = 3$;
• $9 = 3^2, GCD = 2$.

The rest have $GCD = 1$.

以下是不超过 $10$ 的非优雅数列表：

• $4 = 2^2$，$\mathrm{GCD} = 2$；
• $8 = 2^3$，$\mathrm{GCD} = 3$；
• $9 = 3^2$，$\mathrm{GCD} = 2$。

其余数的 $\mathrm{GCD} = 1$。