题目描述

有$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$。