Ugly Number II

Hard

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the n-th ugly number. (The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... begins with 1.)

Example 1

Input:  n = 10
Output: 12

Example 2

Input:  n = 1
Output: 1

Constraints

• 1 <= n <= 1690