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.

Example 1:

Input:  10
Output: 12

(Ugly numbers: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...)

Example 2:

Input:  1
Output: 1

Constraints:

• 1 ≤ n ≤ 1690

Input format: A single integer n.

Output format: The nth ugly number.