#include<fstream>
using namespace std;

const int Z = 9973;
const int C = 1005100;

int ci[C+2],v[C];
int inv[Z+2];
int nr,s;

int u;

inline int minus1(int a,int b)
{
    int r = (a-b) % Z;
    if(r>=0) return r;
    return Z+r;
}

void euclid(int a,int b,int &x,int &y,int &d)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
        return;
    }
    int x1,y1,q=a/b;
    euclid(b,a%b,x1,y1,d);

    x=y1;
    y=x1-q*y1;
}

void ciur()
{
    int i,j;
    ci[1]=true;
    for(i=2;i*i<C;i++)
        if(!ci[i])
            for(j=i*i;j<C;j+=i)
               ci[j]=true;
    for(i=1;i<C;i++)
        if(!ci[i])
            v[++u]=i;

}


void desc(long long n)
{
    nr=s=1;
    int i,p,ct;
    for(i=1;(long long)v[i]*v[i]<=n;i++)
    {
        if(n%v[i]!=0)
            continue;

        p=v[i];
        ct=1;

        while(n%v[i]==0)
        {
            ct++;
            p=p*v[i]%Z;
            n/=v[i];
        }

        nr*=ct;
        s=(s*minus1(p,1)%Z*inv[minus1(v[i],1)])%Z;

    }
    if(n!=1)
    {
        nr*=2;
        s=s*(n+1)%Z;
    }
}




ifstream in("ssnd.in");
ofstream out("ssnd.out");
int main()
{
    //freopen("ssnd.in","r",stdin);
    //freopen("ssnd.out","w",stdout);
    int i,x,y,d,t;
    long long n;
    for(i=1;i<Z;i++)
    {
        if(inv[i] != 0) continue;
        euclid(i,Z,x,y,d);
        x %= Z;
        if(x>=0)
        {
            inv[i] = x;
            inv[x] = i;
        }
        else
        {
            inv[i] = x+Z;
            inv[x+Z] = i;
        }

    }

    ciur();
    in>>t;
    for(i=1;i<=t;i++)
    {
        //s=1;
        in>>n;
        desc(n);
        out<<s<<" "<<n<<"\n";
    }
    return 0;
}