f=->a,b{r=1
a<1||(1..11).find{r<=(c=a%r<<=4)&&c<b&&f[a/r,c]}}
loop{p f[gets.hex,1<<44]}