题目描述

有一个魔法密码盘，上面显示着一个十进制正整数。

最开始，密码盘上显示的是 $1$。你可以对当前显示的数字 $x$ 进行以下两种操作之一：

• 启动增幅装置，将数字变为 $x \times a$。
• 启动旋转装置，将数字的最后一位移动到最前面。

但是，旋转装置只有在满足以下条件时才能使用：

• 当前数字至少是两位数，即 $x \ge 10$；
• 当前数字的最后一位不是 $0$。

例如，当 $a = 2$，当前数字为 $123$ 时：

• 使用增幅装置，可以将 $123$ 变为 $246$；
• 使用旋转装置，可以将 $123$ 变为 $312$。

现在给定整数 $a$ 和目标数字 $N$，请你求出最少需要多少次操作，才能让密码盘显示 $N$。

如果无论如何都无法让密码盘显示 $N$，请输出 $-1$。

输入格式

一行两个整数 $a, N$。

输出格式

输出一个整数，表示最少操作次数。

如果无法达到目标，输出 $-1$。

样例

3 72

4

2 5

-1

2 611

12

样例1解释

一种最优操作方案如下：

$1 \to 3 \to 9 \to 27 \to 72$

前三次使用增幅装置，最后一次使用旋转装置。

数据范围

对于 $100\%$ 的数据，$2\le a,\ N< 10^6$。