In Q (27 characters)


f:{$[0=x;1;(*/)9h$1+til x]}

Computes in less than one millisecond

q)\t f 125

0