Let p (i) be the i-th prime number from the smallest. For example, 7 is the fourth prime number from the smallest, 2, 3, 5, 7, so p (4) = 7.

Given n, the sum of p (i) from i = 1 to n s

s = p (1) + p (2) + .... + p (n)

Create a program that outputs. For example, when n = 9, s = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 100.



Input

Given multiple datasets. Each dataset is given the integer n (n ≤ 10000). When n is 0, it is the last input. The number of datasets does not exceed 50.

Output

For n in each dataset, print s on one line.

Example

Input

2
9
0


Output

5
100
def prime_checker(n, option = False) -> list:
    p = [False, True, False, False, False, True] * (n // 6 + 1)
    del p[n + 1:]
    p[1 : 4] = False, True, True
    for x in range(5, int(n**.5 + 1)):
        if p[x]:
            p[x * x :: 2*x] = [False] * ((n // x - x) // 2 + 1)
    return [e for e, q in enumerate(p) if q] if option else p

from itertools import accumulate
*p, = accumulate([0] + prime_checker(105010, True))
for i in [*map(int, open(0))][:-1]:
    print(p[i])
