Xét dãy các số nguyên dương mà tổng các chữ số (trong biểu diễn thập phân) chia hết cho số chữ số của chính nó. Liệt kê các số ấy theo thứ tự tăng dần, ta được phần đầu dãy: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 19, 20, …

Yêu cầu: Cho số nguyên dương k, hãy tìm số thứ k của dãy (chỉ số trong dãy bắt đầu là 1).

Dữ liệu vào:

Một dòng ghi số nguyên k (1 ≤ k ≤ 10⁵).

Kết quả:

Một dòng chứa 1 số nguyên là kết quả.

Ví dụ:

DIVN.INP
1

DIVN.OUT
1

DIVN.INP
15

DIVN.OUT
20