H. 你猜是啥筛？

传统题

1000ms

256MiB

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

题目描述

有 $m$ 次询问，每次给你一个 $n$ ，请你输出 $n$ 以内有多少个质数。

第一行一个整数 $m$ ,代表询问次数。

第二行 $m$ 个整数，代表每次询问的整数范围 $n$ 。

一行输出 $n$ 个，每个为 $n$ 以内（包含 $n$ ）的质数个数，用空格隔开。

3
5 7 9

3 4 4

【数据范围】
对于 $100\%$ 的数据， $n = 10^6$ ， $1 \le q \le 6*10^5$ 。