求全部原根的板子：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=1001000;
int prime[maxn],pi[maxn],ans[maxn],cnt=0;
bool ha[maxn],vis[maxn];
int p[110],tot;
void Prime(void)
{
    ha[1]=true;
    pi[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i,pi[i]=i-1;
        for(int j=0;j<cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                pi[i*prime[j]]=pi[i]*prime[j];
                break;
            }
            pi[i*prime[j]]=pi[i]*pi[prime[j]];
        }
    }
    vis[2]=vis[4]=true;
    for(int i=1;i<cnt;i++)
    {
        for(int j=1;j*prime[i]<maxn;j*=prime[i])
        {
            vis[j*prime[i]]=true;
            if(2*j*prime[i]<maxn)
                vis[2*j*prime[i]]=true;
        }
    }

}

int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

int mypow(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

void only(int n)
{
    tot=0;
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        p[++tot]=prime[i];
        while(n%prime[i]==0) n/=prime[i];
    }
    if(n>1) p[++tot]=n;
}

bool check(int g,int n)
{
    if(mypow(g,pi[n],n)!=1) return false;
    for(int i=1;i<=tot;i++)
    {
        if(mypow(g,pi[n]/p[i],n)==1) return false;
    }
    return true;
}

int getmin(int n)
{
    int pm=2;
    while(1)
    {
        if(check(pm,n))
            break;
        pm++;
    }
    return pm;
}

void doit(int g,int n,int d)
{
    int cm=0;
    for(int i=1;i<=pi[n];i++)
    {
        if(gcd(i,pi[n])==1)
            ans[++cm]=mypow(g,i,n);
    }
    sort(ans+1,ans+cm+1);
    printf("%lld\n",cm);
    for(int i=1;i<=cm/d;i++)
        printf("%lld ",ans[i*d]);
    putchar('\n');

}

signed main(void)
{
    Prime();
    int t;
    scanf("%lld",&t);
    while(t--)
    {
        int n,d;
        scanf("%lld%lld",&n,&d);
        if(!vis[n])
        {
            printf("0\n\n");
            continue;
        }
        only(pi[n]);
        doit(getmin(n),n,d);
    }

    return 0;
}