A sequence of integer numbers \textbf{F_r = a_0, a_1, ..., a_n, ...}, is called the Fibonacci sequence modulo \textbf{r} if \textbf{a_0 = 0}, \textbf{a_1 = 1}, and \textbf{a_i = (a_\{i-2\} + a_\{i-1\}) mod r} for all \textbf{i} ≥ \textbf{2}. A number \textbf{p} > \textbf{0} is called the period of the sequence, if there is some \textbf{i_0}, such that for all \textbf{i} ≥ \textbf{i_0} the equation \textbf{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 \textbf{r} you have to find whether the sequence \textbf{F_r} is periodic, and if it is what is its smallest period. \InputFile Input file contains \textbf{a_n} integer \textbf{r} (\textbf{2} ≤ \textbf{r} ≤ \textbf{2·10^9}). \OutputFile If \textbf{F_r} is periodic, print its smallest period to the output file. If it is not, print \textbf{0}.