Một dãy số vô hạn có thể được tạo ra chỉ nhờ phần tử đầu tiên bằng cách sử dụng 3 quy tắc sau:

• Quy tắc ~1~: Phần tử đầu tiên của dãy số của giá trị là ~1~.
• Quy tắc ~2~: Với mỗi phần tử đã biết, ta có thể tính được giá trị của phần tử có chỉ số gấp đôi nó bằng cách cộng thêm ~1~.
• Quy tắc ~3~: Nếu có phần tử nào chưa được tính bằng quy tắc ~2~, thì giá trị của nó sẽ bằng tổng của hai phần tử ở ngay bên trái và bên phải của nó.

Yêu cầu

Cho số nguyên dương ~n~. Tính giá trị của phần tử ở vị trí ~n~ của dãy trên.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ ~(1≤n≤10^{12})~.

Output

Một dòng duy nhất chứa kết quả bài toán.

Sample Input 1

7

Sample Output 1

10

Sample Input 2

8

Sample Output 2

4

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤n≤10^6~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.