Cho một dãy ~F~ dài vô tận. Nguyên tắc xây dựng dãy ~F~ như sau:

• Số đầu tiên bằng ~1~.
• Từ số thứ 2 trở đi, ~F_i = F_{i-1}~ nhân 2, sau đó sắp xếp lại các chữ số trong ~F_i~ theo thứ tự tăng dần. (Các chữ số ~0~ ở đầu ~F_i~ xem như vô nghĩa và có thể xóa chúng đi).

Như vậy các số đầu tiên trong dãy ~F~ là: ~1~, ~2~, ~4~, ~8~, ~16~, ~23~, ~46~ ~...~

Cho số ~n~, bạn hãy tìm số ~F_n~.

Input

• Nhập từ bàn phím số tự nhiên ~n~ ~(1 ≤ n ≤ 10^{15})~.

Output

• In ra số thứ ~n~ của dãy ~F~.

Sample Input

7

Sample Output

46