HZNUOJ

小Q的素数

Tags:
Time Limit:  10 s      Memory Limit:   512 MB
Submission:2113     AC:464     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