Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence  1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...  shows the first 11 ugly numbers. By convention, 1 is included.

Given the integer n,write a program to find and print the n'th ugly number.

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a  line with n=0.

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.