← 返回题目列表

Codeforces · 1036/F

F. 相对主要的权力

中文机器翻译题面 查看原题

考虑一些正整数$$$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$$$。