FN16BASE - Forever Young

My birthday is coming up. Alas, I am getting old and would like to feel young again. Fortunately, I have come up with an excellent way of feeling younger: if I write my age as a number in an appropriately chosen base $b$, then it appears to be smaller. For instance, suppose my age in base $10$ is $32$. Written in base $16$ it is only $20$!

However, I cannot choose an arbitrary base when doing this. If my age written in base $b$ contains digits other than $0$ to $9$, then it will be obvious that I am cheating, which defeats the purpose. In addition, if my age written in base $b$ is too small then it would again be obvious that I am cheating.

Given my age $y$ and a lower bound $\ell $ on how small I want my age to appear, find the largest base $b$ such that $y$ written in base $b$ contains only decimal digits, and is at least $\ell $ when interpreted as a number in base $10$.

Input

Multiple test cases. Please process until EOF is reached. Each test case consists of a single line containing two base 10 integers $y$ ( $10 \le y \le 10^{18}$ – yes, I am very old) and $\ell $ ($10 \le \ell \le y$).

Output

For each test case, display the largest base $b$ as described above in a single line.

Example

Input:
32 20
2016 100

Output:
16
42

Added by:Fudan University Problem Setters
Date:2016-05-20
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:ACM/ICPC World Finals 2016

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.