该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

筛法求素数，指的是每次将一个素数的所有的倍数去掉，如果当前的数没有被比它小的数去掉过，那么当前的数就是素数。 比如1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1不是素数。不用管。 2是素数，那么2的所有的倍数要被去掉。 3是素数，那么3的所有的倍数要被去掉。 4 被去掉了。不用管。 。。。 这样做下去我们就可以筛选出所有的指定范围内的素数了。 你的任务是求小于等于$n$的素数的个数count。 做完这道题后感兴趣的同学可以将n/count 的值打印输出来看看。

输入格式

第一行输入一个整数$T$，表示询问的个数 接下来$T$行每行输入一个整数$n$.

输出格式

对于每个询问$n$输出小于等于$n$的的素数的个数。

2
10
1000000

4
78498

约定：

$1 \le T \le 10^8, 1 \le n \le 1000000$

提示：

要注意$n$和$T$的范围哦，算算自己的程序能不能在$1$秒内算出结果，普通计算机一秒钟大约是$10^7$到$10^8$的计算量