Lonely Numbers

在数字世界中，如果两个不同的数字有很多共同点，但每个数字又各有独特之处，那么它们就是朋友。

更准确地说，两个不同的数字 a 和 b 是朋友，当且仅当 gcd(a,b)、\frac{a}{gcd(a,b)}、\frac{b}{gcd(a,b)} 可以作为三角形的三条边。

三个数 a、b 和 c 能作为三角形的三条边，当且仅当 a + b > c，b + c > a 且 c + a > b。

在一组数字中，如果某个数字在该组中没有任何朋友，则称其为孤独数字。

给定一个包含 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 这一个数字，因此它是孤独的。

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

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