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


import java.util.*;

import java.lang.*;

import java.math.*;



public class Main {

	Scanner sc = new Scanner(System.in);

	void run(){

		boolean[] np = new boolean[500001];

		np[0] = np[1] = true;

		for(int i=0; i< 500001;i++){

			if(np[i]) continue;

			for(int j = i*2; j < 500001; j += i){

				np[j] = true;

			}

		}

		int[] ans = new int[10001];

		int sum=0;

		int j = 0;

		for(int i=0; j<10000;i++){

			if(!np[i]){

				sum+=i;

				j++;

				ans[j] = sum;

			}

		}

		for(;;){

			int n = sc.nextInt();

			if(n==0){

				break;

			}

			System.out.println(ans[n]);

		}

		

	}

	public static void main(String[] args){

		Main m = new Main();

		m.run();

		

	}

}