Uugly Number II

Problem statement

A manufacturing line approves batch sizes that can be assembled using only multiplication by 2, 3 and 5, starting from one unit. The planning catalog lists all approved positive sizes in increasing order without duplicates. Your task Find the nth positive integer whose prime factors are all drawn from 2, 3 and 5. The value 1 is the first entry. Important details Numbers with a prime factor such as 7 are excluded. A value reachable by several multiplication sequences appears only once. Generate the ordered sequence efficiently rather than checking every positive integer up to the answer. Worked example The first seven approved sizes are 1, 2, 3, 4, 5, 6 and 8. Therefore n = 7 produces 8, skipping 7 because it has an unsupported prime factor.

Input format

One integer n.

Output format

Print the nth approved value.

Constraints

1 <= n <= 1690.

Sample input

7

Sample output

8