Tên bài: Xâu Fibo

Anna rất thích tính đối xứng, một phần vì tên cô cũng là một xâu đối xứng. Một xâu được gọi là đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau.

Tại trường, Anna được học về dãy xâu Fibonacci ~ F_0, F_1, F_2, \dots ~ như sau:

• ~ F_1 = \text{'A'} ~
• ~ F_2 = \text{'B'} ~
• ~ F_n = F_{n-1} + F_{n-2} ~ với mọi ~ n \geq 2 ~ (nối hai xâu Fibonacci liền trước lại với nhau).

Như vậy, 5 xâu Fibonacci đầu tiên là: 'A', 'B', 'BA', 'BAB', 'BABBA'.

Anna quan tâm đến vấn đề tìm xâu con đối xứng dài nhất trong xâu Fibonacci ~ F_k ~. Nhiệm vụ của bạn là giúp Anna xác định độ dài của xâu con đối xứng dài nhất trong ~ F_k ~.

Dữ liệu vào

• Gồm một dòng duy nhất là số nguyên ~ k ~ ( ~ 0 \leq k \leq 20 ~ ), được đọc từ file FBS.INP.

Dữ liệu ra

• Ghi ra file FBS.OUT một số nguyên duy nhất là độ dài xâu con đối xứng dài nhất trong xâu Fibonacci ~ F_k ~.

Ràng buộc

• ~ 0 \leq k \leq 20 ~

Ví dụ

Dữ liệu vào (FBS.INP):

3

Dữ liệu ra (FBS.OUT):

1

Dữ liệu vào (FBS.INP):

4

Dữ liệu ra (FBS.OUT):

3

Dữ liệu vào (FBS.INP):

5

Dữ liệu ra (FBS.OUT):

4