Để 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(lo{g}_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$.