A sequence of integer numbers a0, a1, . . . , an, . . . , is called the Fibonacci sequence modulo r if a0 = 0, a1 = 1, and ai = (ai−2 + ai−1) mod r for all i ≥ 2. A number p > 0 is called the period of the sequence, if there is some i0, such that for all i ≥ i0 the equation ai = ai+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 r you have to find whether the sequence Fr is periodic, and if it is what is its smallest period. Constraints: 2 <= r <= 2*10^9

Link to the problem: Problem E.