Count Primes Using the Sieve of Eratosthenes

You are given a number of test cases. For each test case, you are provided with a non-negative integer n. Your task is to calculate the number of prime numbers from 2 up to and including n using the Sieve of Eratosthenes.

The Sieve of Eratosthenes is an efficient algorithm to generate all prime numbers up to a given limit. The algorithm eliminates multiples of each prime number starting from 2. Mathematically, the number of primes up to n can be expressed as:

[ \text{prime_count}(n) = \sum_{i=2}^{n} \mathbf{1}_{{i \text{ is prime}}} ]

Implement the algorithm and output the number of primes for each test case.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n1
n2
... 
nT

Where T is the number of test cases, and each of the following ni is a non-negative integer.

outputFormat

For each test case, output a single integer on a new line representing the number of prime numbers that are less than or equal to n.

## sample

3
10
20
30

4
8
10

</p>