Строки Фибоначчи

시간 제한2초메모리 제한1024 MB

요약

k가 80 이하로 주어질 때, k번째 피보나치 문자열에 포함된 가장 긴 회문 부분열의 길이를 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 수학, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

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

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

$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$ -й строке Фибоначчи.

예제2

예제 1
입력
```
2
```
예상 출력
```
1
```
예제 2
입력
```
4
```
예상 출력
```
4
```