思路

这是一个典型的最短路径问题，可以使用广度优先搜索（BFS来解决。每个状态代表当前的数字，通过应用两种魔法可以到达下一个状态。我们需要找到从 1 到 b 的最短路径(由于状态只有1000000种)。也可以考虑记忆化搜索来做这一道题

算法步骤

1.初始化： 使用一个队列来进行 BFS，初始状态为 1，步数为 0。 使用一个数组 visited 来记录每个数字被访问的最少步数，初始时所有值为 -1（未访问）。

2.BFS 过程：

题目内容

小红最近正在学习魔法，通过魔法可以改变纸上的数字。

小红一共会两种魔法，第一种魔法可以将纸上数字变为它的$a$倍，比如在$a=3$时，他可以将$666$变成$1998$;第二种魔法可以让纸上的数字循环右移一次，比如$12345$在施加第二种魔法后会变成$51234$，$119$会变$911$，需要注意的是，小红无法对小于$10$或是以$0$为结尾的数施加第二种魔法。

纸上的数字初始是$1$，小红想将它变成自己的幸运数字$b$，那么请问小红至少需要施加几次魔法。如果无论如何 都无法将它变成$b$,请输出$-1$。

输入描述

输入一行，包含两个正整数$a,b$ $2≤a,b<10^6$

输出描述

输出一行一个数，表示最少的魔法次数，或输出$-1$表示无解。

样例1

输入

3 621

输出

6

说明

样例解释$1$

一种可行的方法为:$1->3->9->27->72->216->621$

输入样例$2$

$3\ 666$

输出样例2

$-1$