逆元分布，对称性——2020-camp-day5-G

/*
性质1：逆元的对应性
    a*b = 1  =>  b*a = 1 (mod p) 即模p意义下，a的逆元是b，那么b的逆元也是a
性质2：逆元的随机(均匀)分布性
    每个数的逆元都是在[2,p-1]随机散落的

模拟一下符合条件的数出现的情况：
    如果某个数x2的逆元是2，那么x2之后的数都不会再满足条件
    如果某个数x3的逆元是3，x3<x2,那么x3满足条件，反之x3不满足条件
    ...
    依次类推，当xk=2时，这个算法就停止了，因为再往前不会出现更小的xk'
    
又因为对称性，xk=2时的逆元就是xk，所以我们大概只要处理sqrt(p)内的逆元，然后翻转一下即可
        当然判断条件是xk>inv[xk]时break 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 500005
ll p;

int inv[N];
struct Node{
    ll xk,k;
    Node(){}
    Node(ll xk,ll k):xk(xk),k(k){}
};
vector<Node>v; 
map<ll,ll>mp; 
void init(){
    inv[1] = 1;
    int q=sqrt(p);
    for(int i = 2; i < min(q+1000ll,p); i++){ 
        inv[i] = (p - p/i) * 1ll * inv[p % i] % p;
        if(i==2){
            v.push_back(Node(inv[i],i));
            mp[i]=inv[i];
            mp[inv[i]]=i;
        }
        else {
            Node last=v.back();
            if(inv[i]<last.xk){
                v.push_back(Node(inv[i],i));
                mp[i]=inv[i];
                mp[inv[i]]=i;
            }    
        }
        if(i>inv[i])return;
    } 
}

int main(){
    int t;cin>>t;
    while(t--){
        v.clear();
        mp.clear();
        cin>>p;
        if(p==2){
            puts("0");continue;
        }
        init();
        cout<<mp.size()<<'
';
        for(auto x:mp)
            cout<<x.first<<" "<<x.second<<'
';
    }
}