Description

Lele is a clever and diligent child. He always likes to explore patterns of things. One day, he suddenly became interested in the positive integer powers of numbers.

As is well known, the last digit of the positive integer powers of $2$ keeps repeating $2,4,8,6,2,4,8,6…$. We say the last digit of the positive integer powers of $2$ has a cycle length of $4$ (in fact, any multiple of $4$ can be called a cycle length, but we only consider the minimal cycle length). Similarly, the last digits of the positive integer powers of other digits also show similar cycles:

$$\def\arraystretch{1.5} \begin{array}{c|c|c}\hline \textbf{Digit}& \textbf{Cycle} & \textbf{Cycle length} \cr\hline\hline 2 & 2,4,8,6 & 4\cr\hline 3 & 3,9,7,1 & 4\cr\hline 4 & 4,6 & 2\cr\hline 5 & 5 & 1\cr\hline 6 & 6 & 1\cr\hline 7 & 7,9,3,1 & 4\cr\hline 8 & 8,4,2,6 & 4\cr\hline 9 & 9,1 & 2\cr\hline \end{array}$$

Then Lele’s question arises: Is it only the last digit that has such a cycle? For the positive integer powers of an integer $n$, do the last $k$ digits exhibit a cycle? If they do, what is the cycle length?

Note:

1. If some positive integer power of $n$ has fewer than $k$ digits, treat the missing higher digits as $0$.
2. If the cycle length is $L$, then for any positive integer $a$, the last $k$ digits of the $a$-th power of $n$ and the $(a+L)$-th power are the same.

Input Format

One line containing two integers $n$ and $k$. $n$ and $k$ are separated by a single space, indicating that we are to find the cycle length of the last $k$ digits of the positive integer powers of $n$.

Output Format

A single integer representing the cycle length. If no cycle exists, output $-1$.

32 2

4

Hint

【Constraints】

For $30\%$ of the testdata, $k \le 4$.
For $100\%$ of the testdata, $1 \le n < 10^{100}$, $1 \le k \le 100$.

【Source】

NOIP 2005 Junior Problem 4.

Translated by ChatGPT 5