#Jelly, 15 bytes

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

[Try it online!](http://jelly.tryitonline.net/#code=MnLigbkq4oKswrkkK1okRuG5olHhu4tA&input=&args=ODI&debug=on) (Takes 27.084s for me) (Constant time)

###16 bytes, much faster

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

[Try it online!](http://jelly.tryitonline.net/#code=MnIzMCrigqzCuSQrWiRG4bmiUeG7i0A&input=&args=ODI) (Takes 0.947s for me) (Constant time)