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*.

**Example 1:**

Input:n = 10Output:12Explanation:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

**Example 2:**

Input:n = 1Output:1Explanation:1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

**Constraints:**

`1 <= n <= 1690`

class Solution {
public int nthUglyNumber(int n) {
}
}