Cho dãy số ~A~ có các phần tử được đánh chỉ số bắt đầu từ ~0~ được gọi là dãy số đẹp nếu thỏa mãn các điều kiện sau:

• ~A_0=0;A_1=1~
• ~\left\{ \begin{array}{lcl} A_{2i}=A_i\\ A_{2i+1}=A_i+A_{i+1} \end{array}\right.~ ~(i \ge 1)~

Yêu cầu: Hãy tìm số lớn nhất của dãy ~A~ từ vị trí ~0~ đến vị trí ~N~.

Dữ liệu vào

Nhập từ bàn phím một số nguyên dương ~N~ ~(N< 10^9)~.

Kết quả ra

Xuất ra màn hình một số nguyên dương là số lớn nhất trong dãy.

Ví dụ

Dữ liệu

5

Kết quả

3

Dữ liệu

10

Kết quả

4

Giải thích

• Ở ví dụ 1, ~N=5~ ta có dãy số gồm ~6~ phần tử : ~\{0,1,1,2,1,3\}~, trong đó số lớn nhất là ~3~.
• Ở ví dụ 2, ~N=10~ ta có dãy số gồm ~11~ phần tử: ~\{0,1,1,2,1,3,2,3,1,4,3\}~, trong đó số lớn nhất là ~4.~