Cycle Length of Last k Digits in Powers

For any positive integer n, consider the sequence of its positive integer powers. When looking at only the last k digits (padding with zeros on the left if necessary), one might ask whether these trailing digits eventually repeat with a constant cycle. For example, it is well known that the last digit (i.e. when k = 1) of powers of 2 cycles as

[ 2,;4,;8,;6,;2,;4,;8,;6,;\ldots ]

with a minimal cycle length of 4. More generally, we may ask: given two positive integers n and k, does the sequence of the last k digits of n^a (a=1,2,3,…) form a cycle? If so, what is the minimal cycle length L such that for every positive integer a the following holds:

[ n^{a+L} \equiv n^a \pmod{10^k} \quad \text{for all } a \ge 1. ]

Important Note:

• If n^a has fewer than k digits, assume that the number is padded with leading zeros to form a k-digit number.
• If a cycle of length L exists, then for every positive integer a the last k digits of n^a and n^a+L are identical.

Caveat: It turns out that a cycle (in the sense defined above) exists if and only if for each prime factor p of 10 (namely, 2 and 5) the following holds: either n is not divisible by p, or n is divisible by p^k. In other words, if for any p in {2, 5} we have a nonzero exponent r in the prime factorization of n with r < k, then no cycle exists and the answer is -1.

If a cycle exists, one may show that the minimal cycle length L is the smallest positive integer such that

[ n^L \equiv 1 \pmod{M}, \quad \text{where } M = \frac{10^k}{\gcd(n,10^k)}. ]

If n is divisible by 10^k, then n^a is congruent to 0 (mod 10^k) for all a, and the cycle length is defined to be 1.

Your task is to compute the minimal cycle length L if the cycle exists, or output -1 otherwise.

inputFormat

The input consists of a single line containing two positive integers n and k separated by a space.

Constraints (example):

• 1 ≤ n ≤ 10⁹
• 1 ≤ k ≤ 6

outputFormat

Output a single integer representing the minimal cycle length L if it exists. If no cycle exists (i.e. the sequence does not satisfy the property for every a), output -1.

sample

2 1

4