Cho một dãy số A dài vô tận. Dãy số A được xây dựng bởi quy tắc:

• A[1] = 1

• Với mọi i > 1, đầu tiên ta lấy A[i] = A[i – 1] * 2, sau đó sắp xếp các chữ số trong A[i] theo thứ tự tăng dần. (Các chữ số 0 ở đầu A[i] nếu có thì coi như là không có nghĩa và có thể xóa đi).

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

Yêu cầu: Cho số n, bạn hãy tìm số A[n].

Input:

Số nguyên dương n (1 ≤ n ≤ 109).

Output:

Một số nguyên dương duy nhất là số thứ n trong dãy A.

Input
7
Output:
46