Fibonacci Strings

Alla loves palindromes. Her name is a palindrome itself. A string is a palindrome if it reads the same from left to right and from right to left.

One day a teacher at school told Alla about so-called Fibonacci strings.

Fibonacci strings are defined as follows:

• $f_0 = a$
• $f_1 = b$
• $f_n = f_{n-1} f_{n-2}$ for every $n \ge 2$, the concatenation of the two previous Fibonacci strings.

So the first five Fibonacci strings are a, b, ba, bab, and babba.

Alla wants to know the longest palindrome that appears in the $k$-th Fibonacci string. Help her solve this problem.

The first line contains one integer $k$ ($0 \le k \le 80$), the index of the Fibonacci string.

Print the length of the longest palindrome contained in the $k$-th Fibonacci string.