#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=1e5+10;
int vis[maxn];
bool done[maxn];
vector<int> e[maxn];
int main(){
	ios::sync_with_stdio(false);	
	cin.tie(0);
	vector<int> zhi;
	for(int i=2;i<=1e5;i++){
		if(!vis[i]) {
			zhi.push_back(i);
		}
		for(int j=0;j<zhi.size()&&i*zhi[j]<=1e5;j++){
			vis[i*zhi[j]]=zhi[j];
			if(i%zhi[j]==0) {
				break;
			}
		}
	}
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		for(int i=1;i<=n;i++){
			e[i].clear();
			done[i]=false;
		}
		int fr=0;
		for(int i=1;i<=n;i++){
			int tmp=i;
			while(vis[tmp]) {
				int now=vis[tmp];
				fr=max(fr,now);
				e[now].push_back(i);
				while(tmp%now==0) {
					tmp/=now;
				}
			}
			if(tmp!=1) {
				e[tmp].push_back(i);
				fr=max(fr,tmp);
			}
		}
		vector<pair<int,int> >ans;
		for(int i=1;i<=fr;i++){
			stack<int> s;
			for(int j=0;j<e[i].size();j++){
				if(!done[e[i][j]]) {
					if(s.empty()){
						s.push(e[i][j]);
					}
					else {
						ans.push_back(pair<int,int>(s.top(),e[i][j]));
					    done[s.top()]=true;
						done[e[i][j]]=true;
						s.pop();
					}
				}
			}
		}
		cout<<ans.size()<<" ";
		for(int i=0;i<ans.size();i++){
			cout<<ans[i].first<<" "<<ans[i].second<<" ";
		}
		cout<<"\n";
	}
}