#Jelly, 14 bytes

2 bytes thanks to Dennis.

    R‘*€¹$+Z$FṢQị@

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

### Original 16-byte answer

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

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