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$