Counting Primes

You are given an integer m and you need to determine the number of prime numbers less than or equal to m. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For m < 2, the answer is 0.

The input consists of multiple test cases. For each test case, you will be given an integer m and you must compute the number of primes up to and including m using an efficient algorithm (such as the Sieve of Eratosthenes). The result for each test case should be output on a new line.

The formula for the number of primes up to m can be expressed as:

\[ \pi(m) = \#\{p \le m : p \text{ is prime}\} \]

inputFormat

The first line of the input contains a single integer T (the number of test cases). Each of the following T lines contains a single integer m, for which you need to calculate the number of primes less than or equal to m.

Example:

3
10
25
1

outputFormat

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

Example:

4
9
0

## sample

3
10
25
1

4
9
0

</p>