AT_abc235_d [ABC235D] Multiply and Rotate

有一个正整数 $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$。

输入以如下格式从标准输入读入。 > $a$ $N$

请输出答案。

## 限制条件 - $2 \leq a < 10^6$ - $2 \leq N < 10^6$ - 输入均为整数。 ## 样例解释 1 通过如下操作，可以在 $4$ 次操作内将黑板上的数从 $1$ 变为 $72$： - 执行第 $1$ 种操作，黑板上的数变为 $1 \to 3$。 - 执行第 $1$ 种操作，黑板上的数变为 $3 \to 9$。 - 执行第 $1$ 种操作，黑板上的数变为 $9 \to 27$。 - 执行第 $2$ 种操作，黑板上的数变为 $27 \to 72$。 无法在 $3$ 次及以下操作内变为 $72$，因此答案为 $4$。 ## 样例解释 2 无论如何操作，都无法将黑板上的数变为 $5$。 ## 样例解释 3 通过合理选择操作，可以按如下顺序 $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$，共 $12$ 次操作将黑板上的数变为 $611$，且这是最少次数。 由 ChatGPT 4.1 翻译