题目描述

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.