102353: [AtCoder]ABC235 D - Multiply and Rotate

Problem Statement

We have a positive integer $a$. Additionally, there is a blackboard with a number written in base $10$.
Let $x$ be the number on the blackboard. Takahashi can do the operations below to change this number.

• Erase $x$ and write $x$ multiplied by $a$, in base $10$.
• See $x$ as a string and move the rightmost digit to the beginning.
  This operation can only be done when $x \geq 10$ and $x$ is not divisible by $10$.

For example, when $a = 2, x = 123$, Takahashi can do one of the following.

• Erase $x$ and write $x \times a = 123 \times 2 = 246$.
• See $x$ as a string and move the rightmost digit 3 of 123 to the beginning, changing the number from $123$ to $312$.

The number on the blackboard is initially $1$. What is the minimum number of operations needed to change the number on the blackboard to $N$? If there is no way to change the number to $N$, print $-1$.

Constraints

• $2 \leq a \lt 10^6$
• $2 \leq N \lt 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$a$ $N$

Output

Print the answer.

Sample Input 1

3 72

Sample Output 1

4

We can change the number on the blackboard from $1$ to $72$ in four operations, as follows.

• Do the operation of the first type: $1 \to 3$.
• Do the operation of the first type: $3 \to 9$.
• Do the operation of the first type: $9 \to 27$.
• Do the operation of the second type: $27 \to 72$.

It is impossible to reach $72$ in three or fewer operations, so the answer is $4$.

Sample Input 2

2 5

Sample Output 2

-1

It is impossible to change the number on the blackboard to $5$.

Sample Input 3

2 611

Sample Output 3

12

There is a way to change the number on the blackboard to $611$ in $12$ operations: $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$, which is the minimum possible.

Sample Input 4

2 767090

Sample Output 4

111

问题描述

我们有一个正整数$a$。此外，还有一个用十进制书写数字的黑板。

• 将黑板上的数字$x$擦除，并用十进制写下$x$乘以$a$的结果。
• 将$x$视为一个字符串，将最右边的数字移动到字符串的最前面。
  这个操作只能在$x \geq 10$且$x$不被$10$整除时进行。

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

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

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

约束条件

• $2 \leq a \lt 10^6$
• $2 \leq N \lt 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