haingoctu / prime_sums

Summing up prime numbers using Sieve of Eratosthenes

Prime_sums by Hai Tu

Summing up prime numbers using Sieve of Eratosthenes

Let P(n) denote the sum of the first n prime numbers. For example, P(1) = 2 and P(3) = 10, since the first three prime numbers are 2, 3 and 5, respectively. Write a program to determine the value of the function P(n) for different values of n. The first few prime sums are 2, 5, 10, 17, 28, 41, 58 and 77.

Input

The first line of the input file contains a single positive integer, t (t ≤ 20000), representing the number of test cases. The following t lines contain one positive integer n (n ≤ 10000), representing the prime sum to be computed for the case.

Output

Write out a single integer on a line by itself for each test case, indicating P(n), for the corresponding input value n.

Sample Input

3 1 6 8

Sample Output

2 41 77 Assignment Details