
#include <iostream>
#include <cmath>

int n;
int known_primes[500000];
int pointer = 0;

void dump_known_primes()
{
	for (int i = 0; i < pointer; i++) {
		std::cout << known_primes[i] << ' ';
	}
	std::cout << std::endl;
}

bool get_input()
{
//	std::cout << "get_input\n";
	return (std::cin >> n);
}

// a < known_primes[pointer+1] ÌÍÍÅ
// a ªf©Ç¤©»è·é
bool is_prime(int a)
{
//	std::cout << "is_prime\n";
	for (int i = 0; known_primes[i] <= std::sqrt(a); i++) {
		if (a % known_primes[i] == 0) {
			return false;
		}
	}
	return true;
}

// mçêÄ¢È¢ÌfðT·
void search_next_prime()
{
//	std::cout << "searcn_next_prime\n";
	int a;
	for (a = known_primes[pointer] + 2; !is_prime(a); a += 2);
	pointer++;
	known_primes[pointer] = a;
}

// XXX
int solve(int a)
{
//	std::cout << "solve\n";
	if (a <= known_primes[pointer]) {
//		std::cout << "a: " << a << ' ' << "pointer: " << pointer << std::endl;
		int i = pointer;
		while (a < known_primes[i]) {
//			std::cout << "i: " << i << std::endl;
			i--;
		}
		return i+1;
	} else {
		search_next_prime();
		return solve(a);
	}
}

int main()
{
//	std::cout << "main\n";
	known_primes[0] = 2;
	known_primes[1] = 3;
	known_primes[2] = 5;
	pointer = 2;
	while (get_input()) {
		std::cout << solve(n) << std::endl;
//		dump_known_primes();
	}
	return 0;
}