CF1036F Relatively Prime Powers

设有一个正整数 $x$，其质因数分解形式为 $x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$。 我们称 $x$ 是“优雅”的，如果数列 $k_1, k_2, \dots$ 的最大公约数等于 $1$。例如，$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$，你需要分别解决本题。

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例中 $n$ 的个数。 接下来的 $T$ 行，每行包含一个整数 $n_i$（$2 \le n_i \le 10^{18}$）。

输出 $T$ 行，第 $i$ 行输出从 $2$ 到 $n_i$ 的优雅数的个数。

以下是 $10$ 以内所有非优雅数的列表： - $4 = 2^2, GCD = 2$； - $8 = 2^3, GCD = 3$； - $9 = 3^2, GCD = 2$。 其余数的 $GCD = 1$。 由 ChatGPT 4.1 翻译