Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.



Input

Input consists of several datasets. Each dataset has an integer n (1 ≤ n ≤ 999,999) in a line.

The number of datasets is less than or equal to 30.

Output

For each dataset, prints the number of prime numbers.

Example

Input

10
3
11


Output

4
2
5
import java.util.Arrays;
import java.util.Scanner;

public class  Main
{
	public static void main(String arg[])
	{
		Scanner sc = new Scanner(System.in);

		while(sc.hasNext())
		{
			int n = sc.nextInt();
			int ans =0;
			boolean a[] = new boolean [n+1];
			Arrays.fill(a, true);
			a[0]=a[1]=false;

			for (int p=2; p*p<=n; p++) 
			{
				if (!a[p]) 
					continue;
				for (int j = p+p; j<= n; j += p)   //合成数jを消す
				{ 
					a[j] = false;
				}
			}
			for(int i =0; i<=n; i++)
			{
				if(a[i])
					ans++;
			}
			System.out.println(ans);
		}
	}

}