問題文

正の整数 $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$

出力

答えを出力せよ。

---

入力例 1

3 72

出力例 1

4

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

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

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

---

入力例 2

2 5

出力例 2

-1

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

---

入力例 3

2 611

出力例 3

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$ に変化させることができ、これが最小です。

---

入力例 4

2 767090

出力例 4

111