6027: 质数数量
[Creator : ]
Description
质数（prime number）又称素数，有无限个，质数定义为在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数。
例如小于 $10$ 的质数有 $2,\ 3,\ 5,\ 7$。
Input
第一行输入一个整数 $T\ (1 \leq T \leq 10^8)$，表示询问的个数
接下来 $T$ 行每行输入一个整数 $n\ (1 \leq n \leq 10^6)$。
接下来 $T$ 行每行输入一个整数 $n\ (1 \leq n \leq 10^6)$。
Output
对于每个询问输出小于等于 $n$ 的的质数的个数。
Sample 1 Input
2
10
1000000
Sample 1 Output
4
78498