Multiply and Rotate

题目描述

有一个正整数 $a$。黑板上写着一个十进制的数。

当黑板上当前写着的数为 $x$ 时，xax可以进行以下任意一种操作，改变黑板上的数：

• 擦掉 $x$，并将 $x$ 乘以 $a$ 的结果以十进制写在黑板上。
• 将 $x$ 视为字符串，把末尾的数字移动到字符串的开头。
  但只有当 $x \geq 10$ 且 $x$ 不能被 $10$ 整除时，才能进行此操作。

例如，当 $a = 2, x = 123$ 时，xax可以进行以下任意一种操作：

• 擦掉 $x$，写上 $x \times a = 123 \times 2 = 246$。
• 将 $x$ 视为字符串，把 123 的末尾数字 3 移到开头。黑板上的数会从 $123$ 变为 $312$。

最开始，黑板上写着 $1$。请问最少需要多少次操作，才能将黑板上的数变为 $N$？如果无论如何都无法将黑板上的数变为 $N$，请输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

$a$ $N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 72

输出 #1

4

输入输出样例 #2

输入 #2

2 5

输出 #2

-1

输入输出样例 #3

输入 #3

2 611

输出 #3

12

输入输出样例 #4

输入 #4

2 767090

输出 #4

111

说明/提示

限制条件

• $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$，且这是最少次数。