def is_smooth(x):
    """Whether x is a good candidate for FFT. We heuristically require
    it to be a multiple of 8 and a product of powers of 2, 3, 5 and 7."""
    if x % 8 != 0:
        return False
    for d in [2, 3, 5, 7]:
        while x % d == 0:
            x = x // d
    return x == 1
