珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

屏幕初始显示整数 $1$。给定整数 $a$ 和目标 $N$，每次可以选择一种操作：把当前数乘以 $a$；或者当当前数至少有两位且末位不是 $0$ 时，把末位数字移到最高位，例如 $123$ 变为 $312$。

请计算把 $1$ 变成 $N$ 的最少操作次数；如果无法得到，输出 $-1$。

输入格式

输入两个整数 a,N。

输出格式

输出最少操作次数，无法到达输出 -1。

2 10

-1

3 1247

-1

4 2484

-1

数据范围与约定

• $2 \le a < 10^6$
• $2 \le N < 10^6$