D - 乘法和旋转

得分：400 分

问题描述

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

• 删除 $x$，并将 $x$ 乘以 $a$，以十进制表示。
• 将 $x$ 视为一个字符串，并将最右边的数字移到最前面。
  只有当 $x \geq 10$ 且 $x$ 不可被 $10$ 整除时，才可以进行此操作。

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

• 删除 $x$，并将 $x \times a = 123 \times 2 = 246$。
• 将 $x$ 视为一个字符串，并将最右边的数字 3 从 123 移到最前面，将数字从 $123$ 改变为 $312$。

黑板上的数字最初为 $1$。将黑板上的数字改变为 $N$ 需要多少次操作？如果无法将数字改变为 $N$，则输出 $-1$。

约束条件

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

输入

从标准输入获取的输入如下所示：

$a$ $N$

输出

输出答案。

3 72

4

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

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

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

2 5

-1

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

2 611

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$，这是最小可能的操作次数。

2 767090

111