Fibonacci Period#5674
A sequence of integer numbers
F_r = a_0, a_1, \ldots, a_n, \ldots,
is called the Fibonacci sequence modulo if a_0 = 0, a_1 = 1, and a_i = (a_{i-2} + a_{i-1}) \bmod r for all i \geq 2.
A number p > 0 is called the period of the sequence, if there is some i_0, such that for all i \geq i_0 the equation a_i = a_{i+p} is satisfied. The sequence is called periodic if it has a period. Clearly, if the sequence is periodic, it has the smallest period.
Given you have to find whether the sequence F_r is periodic, and if it is what is its smallest period.
Input file contains integer (2 \leq r \leq 2 \cdot 10^9).
If F_r is periodic, print its smallest period to the output file. If it is not, print .
Example 1