Sau sự cố tại bài thi sát hạch pháp sư hạng nhất, Hiệp Hội Pháp Sư Châu Lục đã quyết định sẽ vĩnh viễn bỏ bài thi này và thay thế bằng một bài thi tương tự, vừa đòi hỏi khả năng sử dụng ma pháp, vừa yêu cầu tư duy toán học đến từ thí sinh. Bài thi được đề ra như sau:

Tìm số tự nhiên \(n\) lớn nhất có các chữ số khác nhau có tổng bằng \(k\).

Input

• Dòng đầu tiên chứa một số tự nhiên \(k\) \((k \leq 45)\).

Output

• Một dòng duy nhất chứa số \(n\).

Example

3

210