#include <fstream>

using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
bool ciur[1000000];long long m,d,i,v[80000],n,x,t,s1,s2,p,j,y;
int main()
{
    ciur[1]=1;ciur[0]=1;
    for(d=2;d<=1000000;d++)
    {
        if(ciur[d]==0)
        {
            for(i=d*d;i<=1000000;i+=d)
                ciur[i]=1;
        }
    }
    for(i=1;i<=1000000;i++)
    {
        if(ciur[i]==0){v[++m]=i;}
    }
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        j=2;
        t=1;
        s1=1;
        s2=1;
        while(v[j]*v[j]<=x&&x>1)
        {
            p=0;
            y=v[j];
            while(x%v[j]==0)
            {
                p++;
                x=x/v[j];
                y*=v[j];
            }
            if(p!=0)
            {
              t*=p+1;
              s1*=y-1;
              s2*=v[j]-1;
            }
            //fout<<v[j]<<" "<<x<<" "<<v[j+1]<<" ";
            j++;
        }
        if(x>1)
        {
            t*=2;
            s1*=x*x-1;
            s2*=x-1;
        }
        //fout<<s1<<" "<<s2<<" ";
        fout<<t<<" "<<(s1/s2)%9973<<'\n';
        //fout<<"KYS";
    }
    return 0;
}