피보나치 문자열

앨라는 팰린드롬을 아주 좋아한다. 이름 자체가 팰린드롬이기 때문이다. 문자열을 왼쪽에서 오른쪽으로 읽든 오른쪽에서 왼쪽으로 읽든 같으면 그 문자열을 팰린드롬이라고 한다.

어느 날 학교 선생님이 앨라에게 피보나치 문자열을 소개해 주었다.

피보나치 문자열은 다음과 같이 정의된다.

• $f_0 = a$
• $f_1 = b$
• 모든 $n \ge 2$에 대해 $f_n = f_{n-1} f_{n-2}$이다. 즉 바로 앞의 두 피보나치 문자열을 이어 붙인 것이다.

따라서 처음 다섯 개의 피보나치 문자열은 a, b, ba, bab, babba이다.

앨라는 $k$번째 피보나치 문자열에 나타나는 가장 긴 팰린드롬이 궁금해졌다. 앨라가 이 문제를 풀도록 도와주자.

첫째 줄에 피보나치 문자열의 번호를 나타내는 정수 $k$ ($0 \le k \le 80$)가 주어진다.

$k$번째 피보나치 문자열에 포함된 가장 긴 팰린드롬의 길이를 출력한다.