eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci Period

Fibonacci Period

Time limit 1 second
Memory limit 64 MiB

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 i2.

A number p > 0 is called the period of the sequence, if there is some i_0, such that for all ii_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 data

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

Output data

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

Examples

Input example #1
2
Output example #1
3
Source Russian Teams Training Sessions in Petrozavodsk, Summer 2004, Andrew Stankevich Contest 8, Thursday, August 26, 2004