#include <stdio.h>
#include <math.h>

bool sosuu[1000000];

int main(void)
{
	int n;
	int sq;
	int i,j;
	int count;
	bool flag;
	int m;

	for(i=2;i<=1000;i++)
	{
		for(j=2;j<=int(1000000/i);j++)
			sosuu[i*j]=true;
	}

	while(~scanf("%d",&n))
	{

		count=0;
		for(m=2;m<=n;m++)
		{
			if(sosuu[m] == false)
				count++;
		}
		printf("%d\n",count);
	}
	return 0;
}
### Prompt

Generate a cpp solution to the following problem:

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

### Response

```cpp
#include <stdio.h>
#include <math.h>

bool sosuu[1000000];

int main(void)
{
	int n;
	int sq;
	int i,j;
	int count;
	bool flag;
	int m;

	for(i=2;i<=1000;i++)
	{
		for(j=2;j<=int(1000000/i);j++)
			sosuu[i*j]=true;
	}

	while(~scanf("%d",&n))
	{

		count=0;
		for(m=2;m<=n;m++)
		{
			if(sosuu[m] == false)
				count++;
		}
		printf("%d\n",count);
	}
	return 0;
}
```