#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<unsigned long,int> nodeType;//first是一个ugly，second是它将要继续乘的数（2，3，5）
int main()
{
unsigned result[1500];//存放ugly number
priority_queue<nodeType,vector<nodeType>,greater<nodeType> >q;//优先队列，由小到大(greater)
//注：pair比较大小，先按first排列，first一样大则比较second
q.push(nodeType(1,2));
for(int i=0; i<1500; i++)
{
nodeType Node=q.top();
q.pop();//把最小的一个（队头）先
result[i]=Node.first;//数组中存入这个ugly
switch(Node.second)//计算由这个ugly推出的ugly
{
case 2:
q.push(make_pair(Node.first*2,2));
case 3:
q.push(make_pair(Node.first*3,3));
case 5:
q.push(make_pair(Node.first*5,5));
}//精妙的设计，这样可以避免重复的ugly
//被2乘上去可以分别乘三个数字，被3乘上去的就不能再乘2，否则可能出现重复，被5乘上去的同理
}
unsigned long n, T, i;
//freopen("data.txt","r",stdin);
cin >> T;
while(T--)
{
cin >> n;//需要第n个not ugly
for(i = 0; i < 1500; ++i)
{//遍历ugly序列，判断每个ugly是否会出现在n个not ugly之间，如果会的话，
//说明第n个not ugly至少在n+1的位子，整体序列长度也会增加
if(result[i] > n)
break;
else
n++;
}//理解为：n个数字中夹杂着ugly，找出第n个not ugly只需要加上n个not ugly之间的ugly就行了。
cout << n << endl;
}
return 0;
}
优先队列的使用方法：http://www.cnblogs.com/TenosDoIt/archive/2013/04/15/3022219.html
