题目描述

我们有一个正整数 $a$。此外，还有一个黑板上的数字，以十进制表示。
设 $x$ 是黑板上的数字。高桥可以通过以下操作来改变这个数字。

• 擦除 $x$ 并将 $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$。

约束条件

• $2 \leq a < 10^6$
• $2 \leq N < 10^6$
• 输入中的所有值都是整数。

---

输入

从标准输入读入数据，输入的格式如下：

$a$ $N$

输出

打印答案。

---

示例输入 1

3 72

示例输出 1

4

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

• 执行第一种操作：$1 \to 3$。
• 执行第一种操作：$3 \to 9$。
• 执行第一种操作：$9 \to 27$。
• 执行第二种操作：$27 \to 72$。

无法在三次或更少的操作中达到 $72$，因此答案是 $4$。

---

示例输入 2

2 5

示例输出 2

-1

无法将黑板上的数字改为 $5$。

---

示例输入 3

2 611

示例输出 3

12

有一种方法可以在 $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$，这是最小可能次数。

---

示例输入 4

2 767090

示例输出 4

111