#include <bits/stdc++.h>
#define mod 9973
using namespace std;
//bool ciur[1000005];
//vector <long long> prime ;
long long i,j,k,nr,t,sd,nrd;

long long expo (long long a, long long b)
{
    long long putere=1;
    while (b)
    {

        if (b&1){putere=(putere*1LL*a)%mod;}
    a=(1LL*a*a);a=a%mod;
    b>>=1;


    putere=putere%mod;
    }
return putere;
}
long long Inv_Mod(long long x)
{

    long long p=expo(x, mod-2);
    return  p;

}

 void solve(long long x, long long &sd,long long &nd)
{
    long long numarator=1LL, numitor=1LL, INV;nd=1;
    long long d=2, putere;
    while (d*d<=x)
    {putere=0;
        if(x%d==0){putere=1;
        while (x%d==0){x/=d;putere++;}
        nd*=putere;nd%=mod;
        numarator=1LL*numarator*(expo(d,putere)-1);
        numitor=1LL*numitor*(d-1);
        numarator=numarator%mod;
        numitor=numitor%mod;

                                          }
    d++;}
    if (x>1){nd*=2;putere=2;d=x;
    numarator*=expo(d,putere)-1;
    numitor*=(d-1);}
    numarator=numarator%mod;
    numitor=numitor%mod;

    INV=Inv_Mod(numitor%mod)%mod;
    sd=(1LL*(numarator*INV )%mod);
}
 int main()
{ ifstream f("ssnd.in");
f>>t;
ofstream g("ssnd.out");
for (i=1;i<=t;i++)
{
    f>>nr;
    solve(nr, sd, nrd);
    g<<nrd<<" "<<sd<<endl;
}
    return 0;
}