题目描述

我们有一个正整数 $a$。有一个黑板，上面写着一个十进制正整数。 令 $x$ 为黑板上的数。高桥可以做下列两种操作来改这个数。

• 擦掉 $x$，写上 $x$ 乘以 $a$。
• 把 $x$ 最右边的那个数字移到最左边。这个操作只有在 $x \ge 10$ 且 $x$ 不能被 $10$ 整除时才能进行。

例如, 当 $a=2, x=123$ 时，高桥可以做下列两操作之一：

• 擦掉 $123$，写上 $246$。
• 把 $123$ 改成 $312$。

最初黑板上的数是 $1$。要让黑板上的数变成 $N$，最少要几次操作？若无法做到，输出 $-1$。

限制

• $2≤a<10^6$
• $2≤N<10^6$
• 输入的值都是整数。

输入格式

$a$ $N$

输出格式

输出答案。

3 72

4

2 5

-1

2 611

12