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)\).

Input

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

Output

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

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): Không ràng buộc gì thêm.

Example

11

20