An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. By convention 1 is the first ugly number. The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
Given n, output the nth ugly number (1-indexed).
Input format
One line: a positive integer n.
Output format
One line: the nth ugly number.
Constraints
- 1 <= n <= 1600