Период Фибоначчи
Последовательность целых чисел
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.