Bất kỳ một học sinh chuyên Tin nào cũng được học bài học về cách chuyển đổi hệ thập phân sang hệ nhị phân. Để tăng thêm tính thú vị về mối quan hệ giữa hệ thập phân và hệ nhị phân, thầy K ra câu đố như sau:

Một số nguyên dương được gọi là số thập nhị (ý là thập phân và nhị phân) nếu biểu diễn ở hệ thập phân của số đó là một hậu tố (phần đuôi) của biểu diễn trong hệ nhị phân của số đó. (Lưu ý biểu diễn ở hệ thập phân và hệ nhị phân trong tình huống này sẽ không có số 0 ở phía đầu). Ví dụ:

(10)₁₀=(1010)₂ 

nhưng số (1010)₁₀=(1111110010)₂ và số (42)₁₀=(101010)₁₀ không phải là số thập nhị

Thầy K tạo ra một danh sách các số thập nhị và đánh số thứ tự từ 1. Hãy tìm số thập nhị thứ n

Input:

Dòng đầu tiên chứa số nguyên dương n (1<=n<10000)

Output

Đưa ra số thập nhị thứ n