Question
Quest for Ugly Numbers
In a quiet village, young Aryan was known for his endless curiosity. He loved spending time with Mrs. Patel, his wise and kind teacher. One afternoon, during a lesson, Mrs. Patel asked the class, “Does anyone here know what an ‘ugly number’ is?” Aryan, always eager to learn, raised his hand and replied, “Ugly numbers are positive integers that are divisible only by 2, 3, or 5.” Impressed with his answer, Mrs. Patel smiled and gave him a challenge: “Can you find the Nth ugly number?” Thrilled by the task, Aryan set off on a journey, determined to uncover the secret of ugly numbers, guided by Mrs. Patel’s wisdom.
Input
The first line of the input contains a single integer N.
Constraints
1 ≤ N ≤ 1690
Constraints
1 ≤ N ≤ 1690
Output
Print the Nth ugly number.
Example
Sample Input
5
Sample Output
5
Explanation
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12,.. ] is the sequence of starting ugly numbers, so the 5th number is 5, Hence the answer is 5.
5
Sample Output
5
Explanation
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12,.. ] is the sequence of starting ugly numbers, so the 5th number is 5, Hence the answer is 5.