在数字世界中,如果两个不同的数字有很多共同点,那么他们就是朋友,而且每个数字都有独特的优势。
更准确地说,如果 $$$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$$$ 是孤独的。