乘与旋转

题目描述

我们有一个正整数 $a$。此外，有一块黑板，上面写着一个十进制数。

设黑板上的数为 $x$。高桥可以通过以下操作来改变这个数。

• 擦去 $x$，写上 $x$ 乘以 $a$ 后得到的十进制数。

• 把 $x$ 看作字符串，将最右边的数字移到开头。

  该操作仅在 $x \ge 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$

输出格式

输出答案。

样例

3 72

4

可以通过如下 4 次操作将黑板上的数从 $1$ 变为 $72$。

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

无法在 3 次或更少的操作内到达 $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

数据范围

• $2 \le a \lt 10^6$
• $2 \le N \lt 10^6$
• 输入中的所有值均为整数。