Mỗi từ trong ngôn ngữ của bộ tộc \(Mumba\) hình thành từ các ký tự \(a\) và \(b\) theo quy tắc sau:

• Không chứa 2 ký tự \(b\) liên tiếp,
• Không có ba từ con giống nhau đứng liên tiếp trong một từ, như vậy aaa không phải là một từ (có 3 từ con \(a\) liên tiếp), \(aabababa\) cũng không phải là một từ (có 3 từ con \(ab\) liên tiếp).

Tất cả các xâu thỏa mãn những điều kiện trên đều là từ trong ngôn ngữ \(Mumba.\)

Yêu cầu: Cho số nguyên \(k (1 ≤ k ≤ 10^5)\). Hãy xác định số từ trong ngôn ngữ Mumba có độ dài đúng bằng \(k.\)

Dữ liệu: Gồm một dòng chứa số nguyên \(k\).

Kết quả: Một số nguyên – kết quả tìm được.

Ví dụ:

Input

5

Output

7

Ràng buộc

• 30% số test ứng 30% số điểm có \(k≤20\)
• 60% số test ứng 60% số điểm có \(k≤25\)