You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

求 $1,2,\cdots,N$ 中素数的个数。

输入格式

有多组测试样例，第一行输入一个整数T，代表测试样例的数量。 对于每一组测试样例： 输入一行一个整数 $N$。

输出格式

对于每一组测试样例： 一行一个整数，表示素数的个数。

输入输出样例 #1

输入 #1

1
10

输出 #1

4

说明/提示

对于 $100\%$ 的数据，$1 \le N \le 10^7$，$1 \le T \le 10^5$。