Problem
A fact you may have noticed about factorials is that as \$n\$ gets larger \$n!\$ will have an increasing number of \$0\$s at the end of it's base \$10\$ representation. In fact this is true for any base.
In this challenge you will be given a base \$b > 1\$ and an integer \$n > 0\$ and you will determine the smallest \$x\$ such that \$x!\$ has at least \$n\$ trailing \$0\$s in its base \$b\$ representation.
Of course you can easily do this by just checking larger and larger factorials. But this is super slow. The actual challenge is to do this quickly. So in order to be a valid answer you must have a worst case asymptotic complexity of \$O(\log(n)^3)\$ where \$n\$ is the number of trailing \$0\$s and \$b\$ is fixed. You should assume that basic arithmetic operations (addition, subtraction, multiplication, integer division, and modulo) are linear to the number of bits in the input.
This is code-golf so the goal is to minimize your source code as measured in bytes.
Examples
For a small example if \$b=2\$ and \$n=4\$ then the answer is \$6\$ since \$5!=120\$ which is not divisible by \$2^4=16\$, but \$6!=720\$ which is divisible by \$16\$.
For a bigger example if \$b=10\$ and \$n=1000\$ then the answer is \$4005\$, since \$4004!\$ has only \$999\$ trailing zeros in base 10, and multiplying by \$4005\$ is obviously going to introduce another \$0\$.