You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n'th ugly number.

翻译：质数因子只有2 3 5的数称为丑数，（规定1也是丑数），让我们找出来第n个丑数。

输入格式

The first line of input contains one positive integer t. Then t lines follow.

Each line contains a number n

翻译：T组输入，每组数据输入一个数字n表示要输出第n个丑数（1<=T<=100,1<=n<=1500)

输出格式

For each line, output the n’th ugly number .

翻译：每组数据输出一行，输出第n个丑数

样例

3
1
2
9

1
2
10

Limitation

1s, 1024KiB for each test case.