#!/usr/bin/env python3

from math import sqrt

def main(lim, x):
    sieve = [False, True] * (lim//2 + 1)
    primes = []
    sub_lim = int(sqrt(lim) + 1)
    count = [[1], [0], [1]]
    even = False
    for n in range(3, lim + 1):
        if sieve[n]:
            primes.append(n)
            for j in range(n**2, lim + 1, 2*n):
                sieve[j] = False
        count.append([int(even)])
        for i, p in enumerate(primes, 1):
            if p > n - p:
                count[n].append(count[n - p][-1] + count[n][-1])
            else:
                count[n].append(count[n - p][i] + count[n][-1])
        if count[n][-1] - int(sieve[n]) > x:
            return n, count[n][-1] - int(sieve[n])
        even = not even
    return False

if __name__ == '__main__':
    lim = 10**6
    x = 5000
    print(main(lim, x)[0])