Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Note that 1 is typically treated as an ugly number.

Examples

Example 1:

Input: n = 10

Output: 12

Explanation: The first 10 ugly numbers are [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]. The 10th ugly number is 12.

Example 2:

Input: n = 1

Output: 1

Explanation: 1 is the first ugly number by convention.

Example 3:

Input: n = 11

Output: 15

Explanation: The first 11 ugly numbers are [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]. The 11th ugly number is 15.

Constraints

• 1 <= n <= 1690