1 of 3

Jelly, 15 bytes

2r⁹*€¹$+Z$FṢQị@

Try it online! (Takes 27.084s for me) (Constant time)

16 bytes, much faster

2r30*€¹$+Z$FṢQị@

Try it online! (Takes 0.947s for me) (Constant time)