Một số nguyên dương được gọi là số ~PDS~ nếu tích các chữ số của nó chia hết cho tổng các chữ số của nó. Gọi ~PDS(N)~ là số ~PDS~ thứ ~N~ (được lập chỉ mục từ ~1~).

Yêu cầu: Tìm ~PDS(N)~.

Dữ liệu vào:

• Gồm một dòng chứa số nguyên dương ~N~. Với ~N \leq 10^9~.

Dữ liệu ra:

• Một dòng chứa kết quả

Ví dụ:

Input

11

Output

20

Giải thích: Các số ~PDS~ từ thứ ~1~ đến thứ ~11~ lần lượt là ~1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20~.

• Subtask 1: 30% số test thỏa ~N \leq 10^3~
• Subtask 2: 30% số test thỏa ~N \leq 10^6~
• Subtask 3: Không có điều kiện gì thêm