题目描述

我们有一个正整数 $a$ 。此外，还有一块黑板，上面写着一个以 $10$ 为底数的数字。 假设 $x$ 是黑板上的数字。高桥可以进行下面的运算来改变这个数字。

• 擦除 $x$ ，写入以 $10$ 为底数的 $x$ 乘以 $a$ 。
• 将 $x$ 看成一个字符串，并将最右边的数字移到开头。 只有当 $x \geq 10$ 和 $x$ 不能被 $10$ 整除时，才能进行此操作。

例如，当 $a = 2, x = 123$ 时，高桥可以进行以下操作之一。

• 删除 $x$ ，写入 $x \times a = 123 \times 2 = 246$ 。
• 将 $x$ 看作一个字符串，并将 123 最右边的数字 3 移到开头，将数字从 $123$ 改为 $312$ 。

黑板上的数字最初是 $1$ 。将黑板上的数字改为 $n$ 所需的最少运算次数是多少？如果无法将数字改为 $n$ ，请打印 $-1$ 。

输入格式

第一行输入两个正整数 $a, n$

输出格式

输出最少操作次数或 -1

3 72

4

2 5

-1

2 611

12

2 767090

111

提示

• $2\ \leq\ a\ \lt\ 10^6$
• $2\ \leq\ n\ \lt\ 10^6$
• 入力はすべて整数である。

Sample Explanation 1

我们可以通过以下四次操作，将黑板上的数字从 $1$ 改为 $72$ 。

• 进行第一种操作： $1 \to 3$ .
• 进行第一种类型的操作： $3 \to 9$ .
• 执行第一种类型的操作： $9 \to 27$ .
• 执行第二种类型的操作： $27 \to 72$ .

不可能通过三次或更少的运算得出 $72$ ，因此答案为 $4$ 。

Sample Explanation 2

不可能将黑板上的数字改为 $5$ 。

Sample Explanation 3

有一种方法可以在 $12$ 次运算中将黑板上的数字改为 $611$ ： $1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 46 \to 92 \to 29 \to 58 \to 116 \to 611$ ，这是可能的最小值。