Toán học luôn mang đến cho người nghiên cứu về nó nhiều điều thú vị, đặc biệt là những dãy số có quy luật. Ví dụ dãy số Fibonacci xuất phát từ bài toán cổ về sự sinh sản của loài thỏ hay dãy số Catalan trong đó số thứ ~ n ~ chính là số cách đặt ~n~ cặp dấu ngoặc mở và đóng sao cho đúng quy tắc ưu tiên tính toán trong biểu thức toán học. Số Catalan thứ ~ n ~ cũng là đáp án của bài toán đếm số cách chia đa giác lồi có ~ n + 2 ~ đỉnh thành các tam giác bằng cách vẽ các đường chéo sao cho chúng không cắt nhau trong đa giác. Tèo rất thích nghiên cứu về các quy luật của dãy số, một hôm anh ấy phát hiện ra dãy số ~ 0, 1, 3, 4, 9, 10,…~ có quy luật: Nếu gọi hai số đầu tiên của dãy là ~ a_0 = 0 ~ và ~ a_1 = 1 ~ thì ~ a_n ~ ~ ( n = 2, 3, 4,…) ~ là số tự nhiên nhỏ nhất không tạo thành một cấp số cộng với bất kỳ hai số nào đứng trước nó trong dãy số.

Yêu cầu: Cho trước số nguyên ~ n ~, bạn hãy tìm số ~ a_n ~ trong dãy số với quy luật như trên.

Dữ liệu vào

• Một số nguyên dương ~ n ~.

Kết quả

• Số nguyên ~ a_n ~ tìm được.

Ràng buộc

• Có 40% số test với ~ 2 ≤ n ≤ 200 ~.
• Có 30% số test với ~ 200 ≤ n ≤ 2000 ~.
• Có 30% số test với ~ 2000 ≤ n ≤ 10^9 ~.

Ví dụ:

Input* 1*

7 

Output* 1*

13