SP709 NICEDAY - The day of the competitors

即将到来的国际信息学奥林匹克竞赛使得越南队的领队需要从全国范围内挑选出最优秀的参赛选手。幸运的是，他们可以从编号为 1 到 $N$ 的 $N$ 名非常优秀的选手中进行选择（这里 $3 \le N \le 10^5$）。一个选手如果他的编号是所有其他选手编号的公约数，就被视为「优秀」选手。

第一行输入一个整数 $t$，表示测试用例的数量（$1 \le t \le 10^4$）。接下来的每一行给出一个整数 $N$，代表选手的总数（$3 \le N \le 10^5$）。

对于每个测试用例，输出优秀选手的数量，结果占一行。 **注意：** 由于输入文件很大，共有 4 个输入文件，总的时间限制为 4 秒（而不是 1 秒）。

满足 $1 \le t \le 10^4$ 且 $3 \le N \le 10^5$。 **本翻译由 AI 自动生成**