质数数量
题号：NC22226
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
例如小于10的质数有2，3，5，7。

输入描述:

第一行输入一个整数T，表示询问的个数

接下来T行每行输入一个整数n.

1<=T<=1e8,1<=n<=1000000

输出描述:

对于每个询问n输出小于等于n的的质数的个数。
示例1

输入

复制 
2
10
1000000

输出

复制 
4
78498