import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); ArrayList prime = new ArrayList(); for(int i = 2; i <= N; i++) { boolean flg = true; for(int j = 2; j * j <= i; j++) { if(i % j == 0) { flg = false; break; } } if(flg) prime.add(i); } int num = prime.size(); // dp[i][j]はjを異なる素数の和で表す(素数0~素数iまでを用いる)場合の、最大の和の回数を表す int[][] dp = new int[num][N + 1]; dp[0][2] = 1; for(int i = 1; i < num; i++) { for(int j = 2; j < N + 1; j++) { if(j >= prime.get(i)) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - prime.get(i)] + 1); } else { dp[i][j] = dp[i - 1][j]; } } } int ans = -1; if(dp[num - 1][N] > 0) ans = dp[num - 1][N]; System.out.println(ans); } }