#679. 循环

循环

题目描述

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。

众所周知,2\red{2}的正整数次幂最后一位数总是不断的在重复24862486\red{2,4,8,6,2,4,8,6……}我们说2\red{2}的正整数次幂最后一位的循环长度是4\red{4}(实际上4\red{4}的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:

循环 循环长度
2\red{2} 2486\red{2、4、8、6} 4\red{4}
3\red{3} 3971\red{3、9、7、1} 4\red{4 }
4\red{4} 46\red{4、6} 2\red{2}
5\red{5} 1\red{1}
6\red{6}
7\red{7} 7931\red{7、9、3、1} 4\red{4}
8\red{8} 8426\red{8、4、2、6} 4\red{4 }
9\red{9} 91\red{9、1} 2\red{2 }

这时乐乐的问题就出来了 :是不是只有最后一位才有这样的循环呢?对于一个整数n\red{n}的正整数次幂来说,它的后k\red{k}位是否会发生循环?如果循环的话,循环长度是多少呢?

注意:

1\red{1}.如果n\red{n}的某个正整数次幂的位数不足k\red{k},那么不足的高位看做是0\red{0}

2\red{2}.如果循环长度是L\red{L},那么说明对于任意的正整数a\red{a}n\red{n}a\red{a}次幂和a+L\red{a + L}次幂的最后k\red{k}位都相同。

输入格式

有一行,包含两个整数n1n<10100\red{n(1 ≤ n < 10^{100})}k1k100\red{k(1 ≤ k ≤ 100)}n\red{n}k\red{k}之间用一个空格隔开,表示要求n\red{n}的正整数次幂的最后k\red{k}位的循环长度。

输出格式

一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出1\red{-1}

样例

输入样例

32 2

输出样例

4

提示

对于30%\red{30 \%}的数据,k4\red{k \leq 4}

对于全部的数据,k100\red{k \leq 100}