HZNUOJ

小Q的素数

Tags:
Time Limit:  10 s      Memory Limit:   512 MB
Submission:2833     AC:875     Score:82.86

Description

小Q特别喜欢素数,他想知道[2, n]内有多少个素数。

素数:只能被1和本身整除的数。

Input

第一行一个正整数T(1 \leq T \leq 10^5),表示有T组数据。
接下来每行包含一个正整数n(2 \leq n \leq 10^3), 表示询问[2, n]内有多少个素数。

Output

输出包含T行,每行包含一个正整数表示[2, n]内有多少个素数。

Samples

input
2 10 20
output
4 8

Hint

题解:https://pasteme.cn/42330

Author

PAN, Lyuzhi