#include<cstdio>
#include<iostream>
using namespace std;
const int nmax=1000000;
const int md=9973;
bool ci[nmax+5];
long long pr[nmax/10],ex[nmax/10],inv[md+5];
long long rlog(long long x,long long p) {
    long long rez = 1;
    x %= md;

    for(; p; p >>= 1) {
        if(p & 1) {
            rez *= x;
            if(rez>=md)
            rez %= md;
        }

        x *= x;
        if(x>=md)
        x %= md;
    }
    return rez;
}
int main()
{
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
    long long t,n,i,j,q,l,nr,sum;
    l=1;
    pr[1]=2;
    for(i=3;i<=nmax;i=i+2)
    {
        if(ci[i]==0)
        {
            l++;
            pr[l]=i;
            for(j=i*i;j<=nmax;j=j+2*i)
                ci[j]=1;
        }
    }
    cin>>t;
    for(q=1;q<=t;q++)
    {
        cin>>n;
        ex[l+1]=0;
        for(i=1;i<=l;i++)
        {
            ex[i]=0;
            while(n%pr[i]==0)
            {
                n=n/pr[i];
                ex[i]++;
            }
        }
        if(n>1)
        {
            ex[l+1]=1;
            pr[l+1]=n;
        }
        nr=1;
        if(ex[l+1]==1)
        l++;
        for(i=1;i<=l;i++)
            nr*=(ex[i]+1);
         sum=1;
         for(i=1;i<=l;i++)
         if(ex[i]>0)
         {
            sum=(sum*((rlog(pr[i],ex[i]+1))-1+md)*(rlog((pr[i]-1),md-2)));
            if(sum>=md)
                sum=sum%md;
         }
        cout<<nr<<" "<<sum<<"\n";
    }
    return 0;
}