提示: 欢迎访问OurACM平台。
Problem 1847 Cycle

Accept: 16    Submit: 98
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

It is well known that the power of 2 is repeated in last 1 digit: 2, 4, 8, 6, 2, 4, 8, 6… We define the cycle length of this sequence to be 4. (Actually all multiples of 4 can be the cycle length, but we choose the minimum positive one.) Similarly, the powers of other numbers have a similar cycle in last 1 digit:

Please find the cycle length of the last k digits for the powers of a positive integer n. If an integer is less than k digits, you may fill 0s before the most significant digit.

Input

Each line contains two integers n (1 <= n < 10^100)and k(1 <= k <= 100), separated by a single space.

Output

For each case, output one integer in a line contains the cycle length. If no such cycle exists, output -1.

Sample Input

32 2

Sample Output

4

Source

FOJ有奖月赛-2009年10月——稚鹰翱翔

Submit  Back  Status  Discuss