Період Фібоначчі

Послідовність цілих чисел

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

називається послідовністю Фібоначчі за модулем r, якщо a_0 = 0, a_1 = 1, і для всіх i ≥ 2 виконується a_i = (a_{i-2} + a_{i-1}) mod r.

Число p > 0 називається періодом послідовності, якщо існує таке i_0, що для всіх i ≥ i_0 виконується a_i = a_{i+p}. Послідовність називається періодичною, якщо вона має період. Очевидно, що якщо послідовність періодична, то вона має найменший період.

Задано r, потрібно визначити, чи є послідовність F_r періодичною, і якщо так, то знайти її найменший період.

Вхідні дані

Вхідний файл містить ціле число r (2 ≤ r ≤ 2·10^9).

Вихідні дані

Якщо F_r є періодичною, виведіть її найменший період у вихідний файл. Якщо ні, виведіть 0.

Приклади