Nth Ugly Number

Given a positive integer (n), your task is to compute the (n\text{-th}) Ugly Number. Ugly numbers are positive numbers whose only prime factors are 2, 3, or 5. The sequence starts with (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, \ldots).

For example, when (n = 10), the output is 12. Please note that the computation should be efficient enough to handle reasonable input sizes.

inputFormat

Input is read from standard input (stdin) and consists of a single integer (n) indicating the position in the Ugly Number sequence.

outputFormat

Output to standard output (stdout) the (n\text{-th}) Ugly Number.## sample

10

12