public class Euler810 {

    static int bitLength(long x) {
        if (x == 0)
            return 0;
        return 64 - Long.numberOfLeadingZeros(x);
    }

    static int nthXorPrimeSieve(int M, long N) {
        long size = 1L << M;
        // Since size could be up to 1<<27, which is 134,217,728, we can use a byte
        // array
        byte[] isPrime = new byte[(int) size];
        for (int i = 0; i < size; i++) {
            isPrime[i] = 1;
        }

        long count = 1;
        if (N == 1)
            return 2;

        for (long i = 3; i < size; i += 2) {
            if (isPrime[(int) i] == 0)
                continue;

            count++;
            if (count == N)
                return (int) i;

            int l = bitLength(i);
            int jStart = l - 1;
            int jEnd = M - l;

            if (jStart > jEnd)
                continue;

            for (int j = jStart; j <= jEnd; ++j) {
                long k = i << j;
                long limit = 1L << j;
                for (long n = 1; n <= limit; ++n) {
                    isPrime[(int) k] = 0;
                    k ^= i * (n & (~n + 1L));
                }
            }
        }
        return 0;
    }

    public static String solve() {
        int ans = nthXorPrimeSieve(27, 5000000L);
        return Integer.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}