#include <fstream>
using namespace std;
const int MOD=9973;
const int N=1000001;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
bool erat[N];
int prime[100003],k;
int n;
void euclid(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        long long x0,y0;
        euclid(b,a%b,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}

void getdiv(long long val)
{
     long long l=1,sol=1,nrdiv=1,p=1;
     int q=0;
     for(int i=1;prime[i]*prime[i]<=val;i++)
     {
         int x=prime[i];
          if(val%x==0)
          {
               q=0;
               p=1;
               l=(l*(x-1))%MOD;
               while(val%x==0)
               {
                    q++;
                    p=(p*x)%MOD;
                    val=val/x;
               }
               p=(p*x)%MOD;
               p=(p+MOD-1)%MOD;
               sol=(sol*p)%MOD;
               nrdiv=nrdiv*(q+1);
               //g<<p<<" "<<l<<"\n";
          }
     }
     if(val>1)
     {
          p=(val*val+MOD-1)%MOD;
          sol=(sol*p)%MOD;
          l=(l*(val-1));
          nrdiv=nrdiv*2;
     }
     long long t1,t2;
     euclid(l,MOD,t1,t2);
     if(t1<0)
     {
         t1=(t1+MOD)%MOD;
     }
     sol=(sol*t1)%MOD;
     g<<nrdiv<<" "<<sol<<"\n";
}
int main()
{
     f>>n;
     long long val;
     int ct=0;
     for(int i=2;i<=N;i++)
     {
         if(erat[i]==0)
         {
             ct++;
             prime[ct]=i;
             for(int j=2;i*j<=N;j++)
             {
                 erat[i*j]=1;
             }
         }
     }
     for(int i=1;i<=n;i++)
     {
          f>>val;
          getdiv(val);
     }
     f.close();
     g.close();
     return 0;
}