#include <iostream>
using namespace std;
const int MAXN = 1005;
long long dp[MAXN], n;

bool isPrime(long long x) {
	for (int i = 2; i < x; i++) {
		if (i % 2 == 0) return false;
	}
	return true;
}
int main() {
	cin >> n;
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			dp[j] = max(dp[j], dp[j - i] + isPrime(i));
		}
	}
	cout << dp[n] << endl;
	return 0;
}