#include <cstdio>
#include <cstring>
using namespace std;
long long bz,ex,s,nr,i,j,n,x,t;
char p[1000000/2/8+1];
int main()
{
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
    n=1000000;
    for(i=1;((i*i)<<1)+(i<<1)<=n;i++)
     {
        if((p[i>>3]&(1<<(i&7)))== 0)
        {
            for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=n;j+=(i<<1)+1)
            p[j>>3]|=(1<<(j&7));
        }
    }
    scanf("%lld",&n);
    for(t=1;t<=n;t++)
    {
        scanf("%lld",&x);
        s=1;
        nr=1;
        if(x==1)
        printf("1 1");
        else if(x==2)
        printf("2 3");
        else if(x==3)
        printf("2 4");
       else
       {
           if(x%2==0)
           {
               ex=1;
               bz=2;
               while(x%2==0)
               {
                   ex++;
                   x/=2;
                   bz=bz*2;
               }
               s=(s*((bz-1)%9973))%9973;
               nr=((nr%9973)*(ex%9973))%9973;
           }
           for(i=1;i*i<=x;i++)
           if((p[i>>3]&(1<<(i&7)))==0)
           {
               ex=1;
               bz=2*i+1;
               while(x%(2*i+1)==0)
               {
                   ex++;
                   x=x/(2*i+1);
                   bz=bz*(2*i+1);
               }
               s=(s*(((bz-1)/(2*i))%9973))%9973;
               nr=((nr%9973)*(ex%9973))%9973;
           }
           if(x>1&&s>1)
           {
               s=(s*(((x*x-1)/(x-1))%9973))%9973;
               nr=nr*2;
               nr=nr%9973;
           }
           else if(x>1&&s==1)
           {
               printf("2 %lld\n",x+1);
           }
           printf("%lld %lld\n",nr,s);
       }
    }
    return 0;
}