在 n>=30000 莫名RE。

#include <bits/stdc++.h>
using namespace std;
bool vis[1500][1500];
stack<int>st;
vector<int>vec[1500];
int t,cnt,prime[6005],h[1500];
bool book[300005];
void init(){
	book[1]=1;
	for(int i=2;i<=300000;i++){
		if(!book[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=300000;j++){
			book[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int check(int n){
	if(n%2==0)return n*(n+1)/2-n/2+2;
	return n*(n+1)/2+1;
	//n*(n+1)/2 n/2-1
}
//int cnt1;
void dfs(int u){
//	cnt1++;
//	cout<<cnt1<<"\n";
//	cout<<u<<"\n";
//	h[u]++;
//	cout<<"iakioi\n";
	for(int i=h[u];i<vec[u].size();i=h[u]){
//		cout<<h[u]<<endl;
		if(vis[u][vec[u][i]]){
			h[u]=i+1;
			continue;
		}
		
		h[u]=i+1;
		
		vis[u][vec[u][i]]=1;
	
		vis[vec[u][i]][u]=1;
//		cout<<i<<" "<<u<<" "<<vec[u][i]<<"\n";
		dfs(vec[u][i]);
		
	}
	st.push(u);
}
void work(){
	int n;
	cin>>n;
//	cout<<n<<endl;
	while(!st.empty())st.pop(); 
	int ans=1;
	while(check(ans)<n)ans++;
//	cout<<ans<<endl;
	for(int i=1;i<=ans;i++)h[i]=0,vec[i].clear();
	for(int i=1;i<=ans;i++)for(int j=1;j<=ans;j++)vis[i][j]=0;
	for(int i=1;i<=ans;i++){
		for(int j=i;j<=ans;j++){
			if(ans%2==0&&i==j-1&&i%2==0)continue;
			vec[i].push_back(j);
			vec[j].push_back(i);
		}
	}
//	cout<<"iakioi"<<endl;
	dfs(1);
	for(int i=1;i<=n;i++)cout<<prime[st.top()]<<" ",st.pop();
	cout<<"\n";
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
    
    init();
    cin>>t;
	while(t--)work();
    return 0; 
}