考虑一些正整数$$$x$$$。其质因数分解的形式为 $$$x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$$$
如果序列 $$$k_1, k_2, \dots$$$ 的最大公约数等于 $$$1$$$,我们称 $$$x$$$ 为优雅。例如,数字 $$$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$$$ 的多个值,对于每个值,您都需要单独解决问题。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^5$$$) — 测试用例中 $$$n$$$ 的值的数量。
接下来的 $$$T$$$ 行包含一个整数 $$$n_i$$$ ($$$2 \le n_i \le 10^{18}$$$)。
输出
打印 $$$T$$$ 行 — 第 $$$i$$$ 行应包含从 $$$2$$$ 到 $$$n_i$$$ 的优雅数字的数量。
示例
输入 #1
4 4 2 72 10
输出 #1
2 1 61 6
注意
以下是 $$$10$$$ 以内的非优雅数字列表:
- $$$4 = 2^2,GCD = 2$$$;
- $$$8 = 2^3,GCD = 3$$$;
- $$$9 = 3^2,GCD = 2$$$。
其余的 $$$GCD = 1$$$。