Background

The starting point that finally ends.
Finally writing the period.
Finally we say goodbye.
Finally we return to the starting point again.
……

An OIer’s contest journey always starts with a NOIp, and most likely also ends with a NOIp, as if the same cycle keeps playing again and again.
If this NOIp is your starting point, then may your OI journey bloom as brilliantly as summer flowers.
If this NOIp is your ending point, then may your OI memories shine like countless stars.
Maybe this is your last time competing on Luogu, maybe not.
But no matter what, good luck in the contest one week later.

Of course, this problem is also related to cycles.

Problem 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