class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if not n:
            return -1

        visited = set([1])
        heap = [1]

        for _ in range(n):
            cur = heapq.heappop(heap)
            for factor in [2, 3, 5]:
                new = cur * factor
                if new not in visited:
                    visited.add(new)
                    heapq.heappush(heap, new)

        return cur