Một số nguyên dương được gọi là số ugly nếu tất cả các ước nguyên tố của nó chỉ thuộc tập \(\{2, 3, 5\}\). Theo quy ước, số \(1\) cũng được coi là số ugly đầu tiên. Dãy các số ugly được sắp xếp tăng dần như sau: \(1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots\)

Hãy tìm số ugly thứ \(N\) trong dãy số trên.

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).

Định dạng đầu ra

• Một số nguyên duy nhất là giá trị của số ugly thứ \(N\).

Ví dụ

Input:

10

Output:

12

Ràng buộc

• 35% số điểm ứng với \(N \le 1000\).
• 65% số điểm còn lại không có ràng buộc gì thêm.