#include<fstream.h>
#include<iostream.h>
#include<math.h>
#define N 1000000
int test,u;
unsigned long long n,d[N],i,j,t,p[N],s,nr,a[N],k,x[N];

long put(unsigned long long x,unsigned long long n)
{if(n==0)
      return 1;
if(n%2==0)
      return put(x,n/2)*put(x,n/2);
else
      return x*put(x,(n-1)/2)*put(x,(n-1)/2);}

void sieve(unsigned long long x[N],unsigned long long *k,unsigned long long p[N],unsigned long long d[N])
{unsigned long long i,nr=0;
for(i=2;i<=1000000;i++)
      {p[i]=0;
      d[i]=0;}
for(i=2;i<=1000000;i++)
if(p[i]==0)
      {nr++;
      x[nr]=i;
      for(j=i+i;j<=1000000;j+=i)
            p[j]=1;}
(*k)=nr;}

int main()
{fstream f1("ssnd.in",ios::in);
fstream f2("ssnd.out",ios::out);
f1>>test;
k=0;
sieve(x,&k,a,d);
for(u=1;u<=test;u++)
     {f1>>n;
     j=1;
     t=n;
     i=1;
     while(t!=1&&i<=k&&x[i]<=sqrt(n))
           {while(t%x[i]==0)
                  {d[j]++;
                  t/=x[i];
                  if(t==1)
                         {p[j]=x[i];
                         j++;}}
           if(d[j]!=0)
                  {p[j]=x[i];
                  j++;}
           i++;}
     if(t!=1)
           {p[j]=t;
           d[j]=1;
           j++;}
     s=1;
     nr=1;
     for(i=1;i<j;i++)
           {nr=nr*(d[i]+1);
           if(d[i]==1)
                 s=s*(p[i]+1);
           else
                 s=s*(put(p[i],d[i]+1)-1)/(p[i]-1);
           d[i]=0;}
     if(s==1)
           {nr=2;
           s+=n;}
     f2<<nr<<" "<<s%9973<<endl;}
f1.close();
f2.close();
return 0;}