Problem Background

The starting point of the end
The point where we write the period
The point where we bid farewell
The point where we return to the origin
…

The competitive journey of every OIer always begins with a NOIp, and often ends with a NOIp, as if repeated cycles are constantly unfolding.
If this NOIp is your starting point, may your OI journey be as splendid as a summer flower.
If this NOIp is your endpoint, may your OI memories be as brilliant as stars.
Perhaps this is your last competition on Luogu, or perhaps not.
However, in any case, may you have good luck in the competition a week later.

Of course, this problem also has something to do with cycles.

Problem Description

The well-known Fibonacci sequence $\mathrm{fib}(n)$ is calculated 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 two preceding terms.

Little F discovered that when each term of the Fibonacci sequence is taken modulo by any integer $M$ greater than 1, the sequence will cycle.

Little F quickly realized that because ($\mathrm{fib}(n - 1) \bmod M$) and ($\mathrm{fib}(n - 2) \bmod M$) can only have $M^2$ possible values, a cycle must occur after $M^2$ calculations.

More generally, we can prove that no matter what modulus $M$ is taken, the Fibonacci sequence modulo $M$ will eventually be $0, 1, \cdots, 0, 1, \cdots$.

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

Input Format

Input consists of a single line containing a positive integer $M$.

Output Format

Output a single line containing a positive integer $n$.

Sample Input and Output

Sample Input #1

2

Sample Output #1

3

Sample Input #2

6

Sample Output #2

24

Notes

Sample 1 Explanation

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots$, and when taken modulo 2, the result is $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 the smallest value of $n$ we are looking for.

Data Range

For 30% of the data, $M \leq 18$;

For 70% of the data, $M \leq 2018$;

For 100% of the data, $2 \leq M \leq 706150 = \text{0xAC666}$.

Hints

If you are not familiar with the modulo operation $(\bmod)$, I am happy to explain that it is the remainder of integer division, which is the "undividable" part of long division, i.e.,
$$a \bmod M = k \iff a = bM + k \ (M > 0, 0 \leq k < M)$$
where $a, b, k$ are non-negative integers.

If you are using C/C++, you can use the % operator for modulo operations.

If you are using Pascal, you can use the mod operator for modulo operations.

见题面 Input 部分

见题面 Output 部分