Prime Counting with Sieve of Eratosthenes

Given a list of integers, your task is to count the number of prime numbers less than or equal to each integer using the Sieve of Eratosthenes algorithm. For each integer \( n \), compute \( \pi(n) \) where \( \pi(n) \) is the number of primes \( \le n \).

You must implement an efficient solution that precomputes the counts of primes up to the maximum provided number. The algorithm has a time complexity of \( O(n \log \log n) \), making it suitable even for large inputs.

inputFormat

Input is provided via standard input (stdin). The first line contains a single integer \( T \) representing the number of test cases. The following \( T \) lines each contain an integer \( n \).

outputFormat

For each test case, output a single integer on a new line: the count of prime numbers less than or equal to the input \( n \).

3
5
10
20

3
4
8