Eternal Youth

Find the largest base b in which y has only decimal digits 0-9 and whose digit string, read as decimal, is at least l.

Medium7MathBinary searchImplementationNo attempts yetTime limit1sMemory limit512 MB

Problem

My birthday is coming up. I have been getting older and I wanted to feel young again, so I found a way to look younger. Pick a suitable base bb, write my age in that base, and the number looks smaller. My age is 32 in decimal, but in base 16 it is only 20.

The base cannot be picked freely. If the age written in base bb contains a single position that is not one of the digits 0 to 9, everybody sees at once that I am cheating and the whole trick is useless.

A value that looks too small is a problem as well. If the written value is far too small, that is obviously cheating too. So I fixed a lower bound ll.

You are given my age yy and the lower bound ll. Find the largest bb such that every position of yy written in base bb is one of the digits 0 to 9, and that representation read as a decimal number is at least ll.

Input

One line with two integers yy and ll, written in decimal. (10y101810 \le y \le 10^{18}, 10ly10 \le l \le y)

Output

Print the largest bb described above.