Sum of Primes using Sieve of Eratosthenes

Given an integer T followed by T test cases, where each test case consists of a single integer n, your task is to compute the sum of all prime numbers less than or equal to n.

You are required to use the Sieve of Eratosthenes algorithm to efficiently find all prime numbers up to the maximum n across the test cases. Then use this sieve to compute the cumulative sum of primes for each query.

For a given integer n, the answer is given by:

$$ S(n)=\sum_{p \leq n} p, $$ where the summation is over all prime numbers \(p\) less than or equal to \(n\).</p>

Input is taken from the standard input and output is printed to the standard output.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the next T lines contains a single integer n (\(1 \le n \le 10^5\)) specifying the bound up to which primes are to be summed.

Example:

2
10
20

outputFormat

For each test case output the sum of all prime numbers less than or equal to n in a new line on the standard output.

Example:

17
77

## sample

2
10
20

17
77

</p>