Để giải bài toán lập trình của mình, Koi đã thiết kế một thoát toán chia để trị như sau, với \(n\) là một số tự nhiên:

def solve(n):
    if(n <= 1): 
        return
    if (n % 2 == 0):
        solve(n/2)
    else:
        solve((n - 1)/2) 
        solve((n + 1)/2)

Tuy nhiên khi chạy thử với \(n\) lớn, Koi để ý rằng thuật toán chạy chậm hơn rất nhiều so với dự tính. Hiển nhiên nếu \(n\) là lũy thừa của \(2\) thì thuật toán sẽ chạy trong \(O(log_2(n))\), Koi muốn tìm những giá trị của \(n\) mà khiến thuật toán của mình chạy chậm nhất - gọi là những số worst case. Số \(n\) là số worstcase khi và chỉ khi với mọi số \(k\) là tham số chuyền cho hàm solve() (trực tiếp hoặc đệ quy từ \(n\)), nếu \(k\) chẵn thì \(k/2\) là số lẻ.

Koi muốn xác định xem số worstcase thứ \(k\) bằng bao nhiêu, các bạn hãy lập trình giúp Koi giải bài toán này nhé.

Đầu vào

Một dòng duy nhất chứa số tự nhiên \(k\).

Đầu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ghi chú: Kết quả đầu ra đảm bảo được đảm bảo là nằm trong phạm vi của số nguyên \(64\) bit.

Ví dụ

Đầu vào:

5

Đầu ra:

6

Giải thích: \(5\) số worstcase đầu tiên là là \(1, 2, 3, 5, 6\).