7339: ABC235 —— D - Multiply and Rotate
[Creator : ]
Description
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.
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.
- 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.
Input
Input is given from Standard Input in the following format:
$a\ N$
$a\ N$
Output
Print the answer.
Constraints
$2≤a<10^6$
$2 \leq N \lt 10^6$
All values in input are integers.
$2 \leq N \lt 10^6$
All values in input are integers.
Sample 1 Input
3 72
Sample 1 Output
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→3.
- Do the operation of the first type: 3→9.
- Do the operation of the first type: 9→27.
- Do the operation of the second type: 27→72.
It is impossible to reach 72 in three or fewer operations, so the answer is 4.
Sample 2 Input
2 5
Sample 2 Output
-1
Sample 3 Input
2 611
Sample 3 Output
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.
2 767090
111