Sum of Primes

Given a positive integer N, calculate the sum of all prime numbers less than or equal to N using the Sieve of Eratosthenes algorithm. You are required to process T test cases. For each test case, output the computed sum on a new line.

Efficient computation is needed since N may be large. All arithmetic involving prime numbers must be performed using the Sieve of Eratosthenes, and care should be taken for the case when N is less than 2.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a single integer N for which the sum of prime numbers up to N is to be computed.

outputFormat

For each test case, output the sum of all prime numbers less than or equal to N on a separate line.

2
10
20

17
77