“丑数”是指除了质因子2,3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
非“丑数”的前10个数为
7, 11, 13, 14, 17, 19, 21, 22, 23, 26, ...
现要求编写一个程序，输出指定第几位的非“丑数”。

第一行为正整数T（T<=10000）, 表示case的数目。
此后T行，每行一个正整数 n (n <= 100000000).

每一个n，输出第n个非“丑数”

3
1
2
9

7
11
23

 题意：

求第n个非丑数

分析：

暴力求解，我们只要求出是丑数的数，那么非丑数就是在丑数和丑数之间了。

吐槽一下，学校oj开1e8+5明明就够了，就是不让过，搞得我搞了半个多小时在找bug

没想到居然得开再大点才过得了，服了

//我用的是紫书上优先队列的方法写的，详细解释可以看我的博客紫书上的丑数，里面有详解
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm> 
using namespace std;
typedef long long ll;
const int N=200000005;
ll a[N];
int nums[3]={2,3,5};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    int t,cnt=0;
    cin>>t;
    priority_queue<ll,vector<ll>,greater<ll> >q;
    set<ll>s;
    ll tmp=1,m=1;
    q.push(1);
    s.insert(1);
    while(cnt<=100000000){
    	tmp=m;
    	m=q.top();
    	q.pop();
    	for(ll i=tmp+1;i<m;++i){
    		a[++cnt]=i;
    		//cout<<a[cnt]<<endl;
		}
		for(int i=0;i<3;++i){
			ll x=nums[i]*m;
			if(!s.count(x)){
				s.insert(x);
				q.push(x);
			}
		}
	}
	
    while(t--){
    	int n;
    	cin>>n;
    	cout<<a[n]<<endl;
	}
    return 0;
}