#include <iostream>
#include <fstream>
#include <bitset>
#define inf 1000008
#define m 9973

using namespace std;

ifstream f("ssnd.in");
ofstream g("ssnd.out");

bitset <inf> ciur;
int nrp[inf],k,n,x;

int lqput(int x,int n){
    int sol=1;
    x=x%m;
    for(; n; n>>=1){
        if(n & 1){
            sol=sol*x;
            sol=sol%m;
        }
        x=x*x;
        x=x%m;
    }
    return sol;
}

void leciur(){
    ciur[0]=1;
    ciur[1]=1;
    for(int i=2; i<inf; ++i){
        if(ciur[i]==0){
            nrp[++k]=i;
            int val=inf/i;
            for(int j=2; j<= val; ++j)
                ciur[j*i]=1;
        }
    }
}

void solve(int a){
    int nrd=1;
    int sum=1;
    for(int i=1; i<=k && nrp[i]*nrp[i]<=a; ++i){
        if(a%nrp[i]==0){
            int p=0;
            while(a%nrp[i]==0){
                ++p;
                a=a/nrp[i];
            }
            nrd=nrd*(p+1);
            cout<<p<<' '<<nrp[i]<<' ';
            int putere1=(lqput(nrp[i],p+1)-1)%m;
            int putere2=lqput(nrp[i]-1,m-2)%m;
            sum=(((sum * putere1)%m)*putere2)%m;
        }
    }
    if(a>1){
        nrd=nrd*2;
        sum=(sum*1LL*(a+1)%m);
    }
    g<<nrd<<' '<<sum<<'\n';
}

int main(){
    f>>n;
    leciur();
    for(int i=1; i<=n; ++i){
        f>>x;
        solve(x);
    }
    return 0;
}