SP10565 ALICESIE - Alice Sieve

Alice 最近学会了使用 Eratosthenes 筛法，这是一种古老的算法，用于找出小于某个上界的所有素数。正如预期的那样，她对这个算法的简洁和优雅感到非常印象深刻。 现在，她决定设计自己的筛法：Alice 筛法；在给定了某个上界 $N$ 的情况下的 Alice 筛法被形式化地定义为以下过程： 1. 创建一个从 $N$ 到 $2$ 的连续整数列表 $(N, N - 1, N - 2, \cdots, 3, 2)$。所有这 $N - 1$ 个数字最初都是未标记的。 2. 最初，让 $P$ 等于 $N$，并保持这个数字未标记。 3. 标记 $P$ 的所有正约数（即 $P$ 保持未标记）。 4. 从 $2$ 到 $P - 1$ 中找到最大的未标记数字，然后让 $P$ 等于这个数字。 5. 如果列表中不再有未标记的数字，则停止。否则，从第 $3$ 步开始重复。 不幸的是，Alice 还没有找到她的筛法的应用。但她仍然想知道，对于给定的上界 $N$，有多少整数会是未标记的。

第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 10 ^ 4$）。接下来的 $T$ 行中的每一行都包含一个整数 $N$（$2 \le N \le 10 ^ 6$）。

输出 $T$ 行，每个测试用例一行，包含所需的答案。 --- Translated by User 735713.