题目描述

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

输出格式

答えを出力せよ。

题目大意

给定两个整数a（2≤a<10^6）,x和N（2≤N<10^6），你可以对这两个数进行以下操作。

·把x乘以a

·将x末尾的数字移动到x的开头（该操作只能在x≥10且x不能被10整除时进行）

例如，当a = 2, x = 123时，你可以进行以下操作。

·将x乘以a，使x变为246

·将x末尾的数字移动到x的开头，使x变为312。

x的初始值为1，你需要用最少的操作次数使a变为N。输出最少的操作次数，如果无解，请输出-1。

3 72

4

2 5

-1

2 611

12

2 767090

111

提示

制約

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