SP5970 FINDPRM - Finding Primes

为了计算从 2 到 \(n\) 范围内的所有素数，一种常用的方法是：从数字 2 开始，将其标记为素数，并把它的所有倍数（不包括它本身）标记为非素数。接着，找到下一个未被标记的最小数，把它标记为素数，并按照同样的方法标记其所有倍数。以此类推，最终得到所有素数的列表。 现在，我们稍微改变一下这个算法：从 \(n\) 开始，而不是从 2 开始的方法。我们将 \(n\) 标记为素数，然后将它的所有因子（不包含它本身）标记为非素数。然后，找到下一个未被标记的最大数，将其标记为素数，并处理它的因子，像之前一样标记它们。重复这个过程，同样可以得到一个素数列表。 你现在想知道，给定一个 \(n\)，有多少个数字同时能在这两种方法中被标记为素数？

第一行是一个整数 \(T\)，表示测试用例的数量。接下来的 \(T\) 行中，每行包含一个整数 \(n\)。

输出包含 \(T\) 行，每行输出一个答案，表示对于每个测试用例，符合条件的数字个数。

1. \(1 \le T \le 100000\) 2. \(2 \le n \le 10000000\) ## 示例 ### 输入 ``` 3 2 4 7 ``` ### 输出 ``` 1 1 2 ``` **本翻译由 AI 自动生成**