Fibonacci Period

A sequence of integer numbers

F_r = a_0, a_1, ..., a_n, ...,

is called the Fibonacci sequence modulo r if a_0 = 0, a_1 = 1, and a_i = (a_{i-2} + a_{i-1}) mod r for all i ≥ 2.

A number p > 0 is called the period of the sequence, if there is some i_0, such that for all i ≥ i_0 the equation a_i = a_{i+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 F_r is periodic, and if it is what is its smallest period.

Input

Input file contains a_n integer r (2 ≤ r ≤ 2·10^9).

Output

If F_r is periodic, print its smallest period to the output file. If it is not, print 0.

Examples