题目描述

编一个程序，计算 $1\sim n$ 范围内素数的个数。输入先给出测试数据组数，再给出每组数据的 $n$。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

接下来 $t$ 行，每行包含一个整数 $n$。

输出格式

对于每组输入的 $n$，输出一行整数，表示 $1\sim n$（包括 $n$）之间的素数的个数。

样例

4
1
10
65
100

0
4
18
25

提示

样例解释

• 第一行输入 $4$，表示共有 $4$ 组测试数据；
• 输入为 $1$ 时，$1$ 到 $1$ 范围内没有素数，输出 $0$；
• 输入为 $10$ 时，$1$ 到 $10$ 之间的素数有 $2,3,5,7$，共 $4$ 个，输出 $4$；
• 输入为 $65$ 时，$1$ 到 $65$ 之间的素数共有 $18$ 个，输出 $18$；
• 输入为 $100$ 时，$1$ 到 $100$ 之间的素数共有 $25$ 个，输出 $25$。

数据范围

$1\le t\le 10^5$，$1\le n\le 10^7$。