AT_abc235_d [ABC235D] Multiply and Rotate

[problemUrl]: https://atcoder.jp/contests/abc235/tasks/abc235_d 正の整数 $ a $ があります。また、黒板に $ 1 $ 個の数が $ 10 $ 進表記で書かれています。 黒板に現在書かれている数を $ x $ としたとき、高橋君は次のいずれかの操作を行い、黒板に書かれている数を変化させることができます。 - $ x $ を消し、 $ x $ を $ a $ 倍した数を $ 10 $ 進表記で新たに書きこむ。 - $ x $ を文字列とみなして、列の末尾の数字を文字列の先頭に移動させる。 ただし、この操作は $ x\ \geq\ 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 $

答えを出力せよ。

### 制約 - $ 2\ \leq\ a\ \lt\ 10^6 $ - $ 2\ \leq\ N\ \lt\ 10^6 $ - 入力はすべて整数である。 ### Sample Explanation 1 以下に説明する操作を行うことで、 黒板に書かれている数を $ 4 $ 回で $ 1 $ から $ 72 $ に変化させることができます。 - $ 1 $ つ目の操作を行う。黒板に書かれている数は $ 1\ \to\ 3 $ に変わる。 - $ 1 $ つ目の操作を行う。黒板に書かれている数は $ 3\ \to\ 9 $ に変わる。 - $ 1 $ つ目の操作を行う。黒板に書かれている数は $ 9\ \to\ 27 $ に変わる。 - $ 2 $ つ目の操作を行う。黒板に書かれている数は $ 27\ \to\ 72 $ に変わる。 $ 3 $ 回以下の操作で $ 72 $ に変化させることはできないため、答えは $ 4 $ になります。 ### Sample Explanation 2 どのように操作しても黒板に書かれている数を $ 5 $ に変化させることはできません。 ### Sample Explanation 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 $ に変化させることができ、これが最小です。