← 返回题目列表

Codeforces · 1423/K

K. 孤独的数字

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

在数字世界中,如果两个不同的数字有很多共同点,那么他们就是朋友,而且每个数字都有独特的优势。

更准确地说,如果 $$$gcd(a,b)$$$、$$$\frac{a}{gcd(a,b)}$$$、$$$\frac{b}{gcd(a,b)}$$$ 可以形成三角形的边,则两个不同的数字 $$$a$$$ 和 $$$b$$$ 是友元。

如果 $$$a + b > c$$$、$$$b + c > a$$$ 和 $$$c + a > b$$$,三个数字 $$$a$$$、$$$b$$$ 和 $$$c$$$ 可以形成三角形的边。

在一组数字中,如果该数字在该组中没有任何朋友,则该数字是孤独的。

给定一组包含 $$$1, 2, 3, ..., n$$$ 中所有数字的数字,该组中有多少数字是孤独的?

输入

第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ - 测试用例的数量。

下一行有 $$$t$$$ 数字, $$$n_i$$$ $$$(1 \leq n_i \leq 10^6)$$$ - 意味着如果 $$$i$$$ 你应该解出数字 $$$1, 2, 3, ..., n_i$$$。

输出

对于每个测试用例,在单独的行上打印答案:$$$1, 2, 3, ..., n_i$$$ 组中孤独数字的数量。

示例

输入 #1

3
1 5 10

输出 #1

1
3
3

注意

对于第一个测试用例,$$$1$$$ 是唯一的数字,因此很孤独。

对于第二个测试用例,其中 $$$n=5$$$,数字 $$$1$$$、$$$3$$$ 和 $$$5$$$ 是孤独的。

对于第三个测试用例,其中 $$$n=10$$$,数字 $$$1$$$、$$$5$$$ 和 $$$7$$$ 是孤独的。