题目描述

在我们周围，有很多令人惊叹的循环现象，比如四季的更替，生命的轮回，以及社会的发展。这些循环，或长或短，但都蕴含着一定的规律。

小码哥是个喜欢探索规律的人。一天，他发现一个有趣的数学现象：整数的正整数次幂在某一位数上的重复性。

对于数字 $2$ 来说：他的整数次幂为 $2^1=2$， $2^2=4$，$2^3=8$，$2^4=16$，$2^5=32$， $2^6=64$， $\dots$，它的个位数会呈现出一个循环的规律： $2, 4, 8, 6, 2, 4, 8, 6 \dots \dots$ 如此循环往复，我们去掉重复的数，所以对于 $2$ 的正整数次幂，周期长度为 $4$ （ $2, 4, 8, 6$ ）。其它整数的正整数次幂在个位数上也有类似的循环现象，它们的周期长度各不相同：

对于数字 $2$，整数 $2$ 的正整数次幂的前 $5$ 个结果：$2, 4, 8, 16, 32$ 循环的最后一位 $2,4,8,6$，所以循环长度为 $4$； 对于数字 $3$，整数 $3$ 的正整数次幂的前 $5$ 个结果：$3, 9, 27, 81,243$ 循环的最后一位 $3,9,7,1$，所以循环长度为 $4$； 对于数字 $4$，整数 $4$ 的正整数次幂的前 $5$ 个结果：$4, 16, 64, 256, 1024$ 循环的最后一位 $4,6$，所以循环长度为 $2$； 对于数字 $5$，整数 $5$ 的正整数次幂的前 $5$ 个结果：$5, 25, 125, 625, 3125$ 循环的最后一位 $5$，所以循环长度为 $1$； 对于数字 $6$，整数 $6$ 的正整数次幂的前 $5$ 个结果：$6, 36, 216, 1296, 7776$ 循环的最后一位 $6$，所以循环长度为 $1$ 、；

小码哥产生了一个疑问：对于一个整数 $n$ 的正整数次幂，除了个位数，它的最后 $k$ 位数是否也会呈现出类似的循环规律呢？如果存在，这个周期的长度又是多少呢？

为了解决这些问题，小码哥去请教了他的老师并获得了一些小提示：如果 $n$ 的某个正整数次幂的位数不足 $k$，我们可以在高位补 $0$；如果周期的长度是 $L$，那就意味着对于任意的正整数 $a$，$n^a$ 和 $n^{a+L}$ 的最后 $k$ 位数是相同的。

输入格式

一行包含两个整数 $n$ 和 $k$（$2 \le n < 10^{100}$；$1 \le k \le 100$），用一个空格隔开。

输出格式

一行包含一个整数，表示循环长度。如果循环不存在，输出 $-1$。

123 2

20

100 2

1