from random import randrange

_small_primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23))

def is_prime(n, k=25):
    n = abs(n)
    if n in _small_primes:
        return True
    for pi in _small_primes:
        if not n % pi:
            return False
    if pow(2, n-1, n) != 1:
        return False
    d, s = n - 1, 0
    while not d % 2:
        d //= 2
        s += 1

    def is_spsp(n, a):
        t = pow(a, d, n)
        if t == 1:
            return True
        for _ in range(s):
            if t == n - 1:
                return True
            t = (t * t) % n
        return False
    return all(is_spsp(n, randrange(2, n-1)) for _ in range(k))


def kalai(n):
    while True:
        s, r, si = n, 1, []
        while s > 1:
            s = randrange(1, s+1)
            if is_prime(s):
                r *= s
                si.append(s)
        if r <= n and randrange(1, n+1) <= r:
            return r, list(reversed(si))

print(kalai(10**30))