#include <stdio.h>
#include <math.h>


using namespace std;

FILE *f=fopen("ssnd.in","r");
FILE *g=fopen("ssnd.out","w");

const int n=1000000;
bool prim[n];
long long  x,nr2;
unsigned long long  b,nr,i,a,p,cnt=0,v[100000];




void ciur()
{
    int i,j;



    for (i=2;i<=n;i++)
        if (!prim[i])
        {
            v[++b]=i;
            cnt++;
            for (j = 2*i;j<=n;j+=i)
                prim[j] = 1;
        }
}







void desc()
{
    long long x,dv=1,sum=1;
    long long  i=0,d;
    long long  cnr=nr;

    for(i=1;i<=b,v[i]<=sqrt(cnr);i++)
    if(nr%v[i]==0)
    {

        d=1;
        x=v[i];
        while(nr%v[i]==0){d++;nr/=v[i];x*=v[i];}
        dv=(long long)(d*dv)%9973;
        if(d>1)
        {

            x--;
            x/=(v[i]-1);
            sum=(sum%9973)*(x%9973)%9973;
        }


    }

    if(nr>1)
    {
        dv=(dv*2)%9973;
        sum=((sum%9973)*((nr+1)%9973))%9973;
        }



    fprintf(g,"%ld ",dv);
    fprintf(g,"%ld\n",sum);



}



int main()
{
    b=0;
    ciur();
    fscanf(f,"%d",&a);
    for(i=1;i<=a;i++)
    {
         fscanf(f,"%ld",&nr);
         if(nr==1) fprintf(g,"%d %d\n",1,1);
         else if(nr<1000000 && prim[nr]==0 )
              fprintf(g,"%d% ld\n",2,(nr+1)%9973);
         else desc();
    }


    fclose(g);
    return 0;
}