29455번 - Строки Фибоначчи 다국어

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи.

Строки Фибоначчи определяются следующим образом:

• $f_0 = a$
• $f_1 = b$
• $f_{n} = f_{n-1} f_{n-2}$ для каждого $n \ge 2$ --- конкатенация двух предыдущих строк Фибоначчи

Таким образом, первые пять строк Фибоначчи: <<a>>, <<b>>, <<ba>>, <<bab>>, <<babba>>.

Аллу сразу заинтересовал вопрос --- какой максимально длинный палиндром встречается в $k$ -й строке Фибоначчи. Помогите Алле решить эту задачу.

Первая строка входного файла содержит одно целое число $k$ ($0 \le k \le 80$) --- номер строки Фибоначчи.

В выходной файл выведите длину самого большого палиндрома, содержащегося в $k$ -й строке Фибоначчи.