Prime Performances

You are given T test cases. For each test case, a positive integer N is provided. Your task is to determine the number of prime numbers in the range from 1 to N. This problem can be solved efficiently using the Sieve of Eratosthenes. The sieve will allow you to quickly compute all prime numbers up to the maximum N among all test cases. You then simply count the cumulative number of primes up to N for each test case.

For example: If N = 10, the primes in the range [1, 10] are 2, 3, 5, and 7, so the answer is 4.

Input/Output Format: The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line contains a single integer T representing the number of test cases. Each of the following T lines contains a single integer N.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁶

outputFormat

For each test case, output a single line containing the number of prime numbers in the range [1, N].

## sample

3
10
20
30

4
8
10

</p>