#include<bits/stdc++.h>
using namespace std;
int n,p;
int o[220000];
int pd[220000];
int inv[220000];
int out[220000],otop;
int zan[2200],ztop=0;
int ans;
int power(long long a,long long b){
	long long RE=1;
	while(b>0){
		if(b&1)RE=RE*a%p;
		b>>=1;a=(a*a)%p;
	}
	return RE;
}
void init(){
	ans=0;
	otop=0;
	ztop=0;
	for(int i=0;i<=p;i++){
		pd[i]=0;
	}
	for(int i=1;i<p;i++){
		inv[i]=power(i,p-2);
	}
}
void sol(){
	scanf("%d%d",&n,&p);
	init();
	for(int i=1;i<=n;i++){
		//scanf("%d",&o[i]);
		o[i]=i-1;
		pd[o[i]]=1;
	}
	if(!pd[0]){
		puts("1 1");
		puts("0");
		return ;
	}
	if(p-n<=2000){
		for(int i=0;i<p;i++){
			if(!pd[i])zan[++ztop]=i;
		}
		for(int i=1;i<p;i++){
			int mex=p;
			for(int j=1;j<=ztop;j++){
				mex=min(mex,(int)(1ll*zan[j]*i%p));
			}
			if(mex>ans){
				ans=mex;
				otop=0;
				out[++otop]=i;
			}
			else if(mex==ans){
				out[++otop]=i;
			}
		}
		printf("%d %d\n",otop,ans);
		for(int i=1;i<=otop;i++){
			printf("%d ",out[i]);
		}printf("\n");
		return ;
	}
	else{
		for(int i=1;i<p;i++){
			int mex=1;
			for(int j=1;j<p;j++){
				int x=1ll*j*inv[i]%p;
				if(!pd[x]){
					mex=j;
					break;
				}
			}
			if(mex>ans){
				ans=mex;
				otop=0;
				out[++otop]=i;
			}
			else if(mex==ans){
				out[++otop]=i;
			}
		}
		printf("%d %d\n",otop,ans);
		for(int i=1;i<=otop;i++){
			printf("%d ",out[i]);
		}printf("\n");
		return ;
	}
}
int main(){
	int T;
	cin>>T;
	while(T--){
		sol();
	}
}