配点 : $400$ 点

問題文

正の整数 $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$ を出力してください。

制約

• $2 \leq a \lt 10^6$
• $2 \leq N \lt 10^6$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$a$ $N$

出力

答えを出力せよ。

3 72

4

以下に説明する操作を行うことで、 黒板に書かれている数を $4$ 回で $1$ から $72$ に変化させることができます。

• $1$ つ目の操作を行う。黒板に書かれている数は $1 \to 3$ に変わる。
• $1$ つ目の操作を行う。黒板に書かれている数は $3 \to 9$ に変わる。
• $1$ つ目の操作を行う。黒板に書かれている数は $9 \to 27$ に変わる。
• $2$ つ目の操作を行う。黒板に書かれている数は $27 \to 72$ に変わる。

$3$ 回以下の操作で $72$ に変化させることはできないため、答えは $4$ になります。

2 5

-1

どのように操作しても黒板に書かれている数を $5$ に変化させることはできません。

2 611

12

適切に操作を選ぶことで、 $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$ に変化させることができ、これが最小です。

2 767090

111