Description

The well-known Fibonacci sequence $\mathrm{fib}(n)$ is computed 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}$$

That is, $0, 1, 1, 2, 3, 5, 8, 13 \cdots$, where each term is the sum of the previous two terms.

Little F discovered that if we take every term of the Fibonacci sequence modulo any positive integer $M$ greater than $1$, the sequence will always become periodic.

Of course, Little F soon understood why: ($\mathrm{fib}(n - 1) \bmod M$) and ($\mathrm{fib}(n - 2) \bmod M$) have at most $M ^ 2$ possible pairs of values, so a cycle must appear within $M ^ 2$ steps.

Even more generally, we can prove that no matter what modulus $M$ we choose, the Fibonacci sequence modulo $M$ will eventually look like $0, 1, \cdots, 0, 1, \cdots$.

Now, given a modulus $M$, please find the smallest $n > 0$ such that $\mathrm{fib}(n) \bmod M = 0$ and $\mathrm{fib}(n + 1) \bmod M = 1$.

Input Format

Input one line containing a positive integer $M$.

Output Format

Output one line containing a positive integer $n$.

2

3

6

24

Hint

Explanation for Sample 1

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots$. After taking modulo $2$, it becomes $0, 1, 1, 0, 1, 1, 0, 1, 1, 0, \cdots$.

We can see that when $n = 3$, $f(n) \bmod 2 = 0$ and $f(n + 1) \bmod 2 = 1$, which is exactly what we need, and it is the smallest such $n$.

Constraints

For $30\%$ of the testdata, $M \leq 18$.

For $70\%$ of the testdata, $M \leq 2018$.

For $100\%$ of the testdata, $2 \leq M \leq 706150=\verb!0xAC666!$.

Notes

If you still do not know what modulo $(\bmod)$ means, I would be happy to tell you. Modulo means taking the remainder of integer division, that is, the part that “cannot be divided evenly” at the end of long division. In other words,

$$a \bmod M =k \iff a = bM + k\ (M > 0, 0 \leq k < M)$$

where $a$, $b$, and $k$ are all non-negative integers.

If you use C / C++, you can use % for modulo.

If you use Pascal, you can use mod for modulo.

Translated by ChatGPT 5