题目描述

丑数是指那些质因数仅为 $2$、$3$ 或 $5$ 的数。以下数列： $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, \cdots$ 展示了前 $10$ 个丑数。按照惯例，$1$ 也被包含在内。

给定整数 $n$，编写一个程序来找出并打印第 $n$ 个丑数。

输入

输入的每一行包含一个正整数 $n$（$n \leq 1500$）。当输入行为 $n = 0$ 时，输入结束。

输出

对于输入中除 $n = 0$ 之外的每一行，输出第 $n$ 个丑数。

输入样例

1
2
9
0

输出样例

1
2
10

题目来源

新西兰 1990 年一级赛，UVA 136