劣质代码，求调教

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,M=1e6+5;
vector<int> pr;
int not_pr[N],g[N],h[N];
void init(){
	for(int i=2;i<=M;i++){
		if(!not_pr[i]){
			pr.push_back(i);
			g[i]=i;
			h[i]=i-1;
		}
		for(int j:pr){
			if(i*j>M) break;
			not_pr[i*j]=1;
			g[i*j]=j;
			if(i%j==0) h[i*j]=h[i]*j;
			else h[i*j]=h[i]*(j-1);
			if(i%j==0) break;
		}
	}
}
int qp(int x,int y,int p){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%p;
		x=x*x%p;
		y>>=1;
	}
	return ans;
}
vector<pair<int,int>> rep(int x){
	vector<pair<int,int>> res;
	while(x>1){
		int w=g[x],cnt=0;
		while(x%w==0) x/=w,cnt++;
		res.push_back({w,cnt});
	}
	return res;
}
int n,d;
bool ok(){
	if(n==2||n==4) return 1;
	auto w=rep(n);
	if(w.size()==1&&w[0].first%2==1) return 1;
	if(w.size()==2&&w[0].first==2&&w[0].second==1) return 1;
	return 0;
}
void sol(){
	cin>>n>>d;
	if(!ok()){
		cout<<"0\n\n";
		return;
	}
	int w=h[n],res=0;
	auto r=rep(w);
	for(int g=1;g<n;g++){
		if(__gcd(g,n)!=1) continue;
		int ok=1;
		for(auto tp:r){
			int u=w/tp.first;
			if(qp(g,u,n)==1){
				ok=0;
				break;
			}
		}
		if(ok){
			res=g;
			break;
		}
	}
	vector<int> ans;
	for(int k=1;k<=w;k++){
		if(__gcd(k,w)==1){
			ans.push_back(qp(res,k,n));
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<"\n";
	for(int i=0;i<(int)ans.size();i++){
		if((i+1)%d==0) cout<<ans[i]<<" ";
	}
	cout<<"\n";
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	int ct;
	cin>>ct;
	while(ct--){
		sol();
	}
}