Pisano Period Reset Finding

The well-known Fibonacci sequence \(\mathrm{fib}(n)\) is defined as follows:

$$ \mathrm{fib}(n)=\begin{cases} 0,& n=0 \\ 1,& n=1 \\ \mathrm{fib}(n-1)+\mathrm{fib}(n-2),& n>1 \end{cases} $$

In other words, the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, …, where each term is the sum of the two preceding numbers.

It is a known fact that for any positive integer \(M>1\), the Fibonacci sequence taken modulo \(M\) eventually becomes periodic, since the pair \((\mathrm{fib}(n-1) \bmod M,\; \mathrm{fib}(n-2) \bmod M)\) can have at most \(M^2\) different values. Thus, a cycle must appear within at most \(M^2\) steps.

Moreover, it can be shown that regardless of which modulus \(M\) is chosen, the Fibonacci sequence modulo \(M\) will eventually exhibit the pattern 0, 1, ....

Your task is: given a modulus \(M\), find the smallest \(n > 0\) such that \(\mathrm{fib}(n) \bmod M = 0\) and \(\mathrm{fib}(n+1) \bmod M = 1\).

inputFormat

The input consists of a single line containing a positive integer \(M\) (where \(M>1\)).

outputFormat

Output the smallest positive integer \(n\) such that \(\mathrm{fib}(n) \bmod M = 0\) and \(\mathrm{fib}(n+1) \bmod M = 1\).

sample

2

3