// Arup Guha
// 11/3/2018
// Solution to 2018 SER D2 Problem: Repeating Goldbachs

import java.util.*;

public class goldbach {
	
	final public static int MAX = 1000000;
	
	public static void main(String[] args) {
		
		// Run prime sieve.
		boolean[] sieve = new boolean[MAX+1];
		Arrays.fill(sieve, true);
		for (int i=2; i<=MAX; i++)
			for (int j=2*i; j<=MAX; j+=i)
				sieve[j] = false;
		
		// Pre-comp everything.
		int[] res = new int[MAX+1];
		res[4] = 1;
		
		// Do the rest.
		for (int i=6; i<=MAX; i+=2) {
			
			// Try largest difference first.
			for (int j=3; 2*j<=i; j+=2) {
				if (sieve[j] && sieve[i-j]) {
					res[i] = res[i-2*j] + 1;
					break;
				}
			}
		}
		
		// Solve it!
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		System.out.println(res[n]);
	}

}