SIOENES - Eratosthenes Prime numbers


Given an integer 'N', print count all the prime numbers which are less than or equal to 'N'.

Input description

First line of input is an integer T (number of testcases) and integer T will be followed by T lines, where each line will contain an integer N.

Output description

Output will consists of T lines. Each line will have count of prime numbers not greater than 'N'.

Constraint

1<=T<=10000

1<=N<=1000000

Example

Input:
2
9
11

output
4
5

hide comments
avanish_1234: 2021-09-27 10:20:13

Yes I also Same thing is happening

codesmiler: 2021-06-18 05:59:40

@ayush_06: May be your code is just working for the given example test case. It should work for all test cases.

For example: if input is
2
3
5

Output should be:
2
3

ayush_06: 2021-06-12 13:37:01

Giving write answer on compiler but after submitting showing wrong answer why??


Added by:codesmiler
Date:2021-06-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All