#include<bits/stdc++.h>
using namespace std;

const int N=1000003;
bool v[N];
int p[N],ph[N];
vector <int> q;
vector <int> ans;
int XXS()
{
	int cnt=0;ph[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!v[i])p[++cnt]=i,ph[i]=i-1;
		for(int j=1;j<=cnt&&i*p[j]<N;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)
			{
				ph[i*p[j]]=ph[i]*p[j];break;
			}
			else
			{
				ph[i*p[j]]=ph[i]*(p[j]-1);
			}
		}
	}
}
void D(int x)
{
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
		{
			q.push_back(i);
			while(x%i==0)x/=i;
		}
	if(x>1)q.push_back(x);
}
int YG(int x)
{
	if(x==2||x==4)return 1;
	if(x%2==0)x/=2;
	for(int i=2;p[i]<=x;i++)
	    if(x%p[i]==0)
	    {
	    	while(x%p[i]==0)
	    	{
	    		x/=p[i];
			}
	    	return x==1;
		}
	return 0;
}
int K(long long a,long long b,long long Mod)
{
	long long s=1;
	for(;b;b>>=1,a=a*a%Mod)
	    if(b&1)s=(s*a)%Mod;
	return s; 
}
int main()
{
	int t;cin>>t;XXS();
	for(int T=1;T<=t;T++)
	{
		int n,d;cin>>n>>d;
		if(!YG(n))
		{
			cout<<0<<'\n'<<'\n';continue;
		}
		q.clear();ans.clear();D(ph[n]);
		int g=0;
		for(int i=1;;i++)
		{
			if(__gcd(i,n)==1)
			{
				bool f=1;
				for(int j=0;j<q.size();j++)
					if(K(i,ph[n]/p[j],n)==1)
					{
						f=0;break;
					}
				if(f)
				{
					g=i;break;
				}
			}
		}
		long long res=1;
		for(int i=1;ans.size()<ph[ph[n]];i++)
		{
			res=res*g%n;
			if(__gcd(ph[n],i)==1)ans.push_back(res);
		}
		sort(ans.begin(),ans.end());
		cout<<ph[ph[n]]<<'\n';
		for(int i=d-1;i<ph[ph[n]]/d*d&&i<ans.size();i+=d)
		    cout<<ans[i]<<" ";
		cout<<'\n';
    }
    return 0;
}