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


using namespace std;

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

const int n=1000001;
bitset <n> prim;
long long  x,nr2,mx=0,mx2;
unsigned long long  b,nr,i,a,p,cnt=0,v[100001],cp,cp2,w[1001];


long long mn(long long a , long long b)
{
    if(a<b) return a; else return b;
}

void ciur()
{
    int i,j;
    v[1]=2;
    b=1;

    for (i=3;i<=mn(mx2,1000);i+=2)
        if (prim[i]==0)
        {
            v[++b]=i;
            cnt++;
            for (j = 2*i;j<=mn(mx,n);j+=i)
                prim[j] = 1;
        }
    for(i=mn(mx2,1000)+1;i<=mn(mx,n);i+=2)
        if(prim[i]==0) v[++b]=i;
}


long long ridic(long long nn, long long put)
{
    int i;
    long long cn=nn,m,cr;
    cr=1;
    for(i=0;i<16;i++)
    {
        m=1<<i;
        if((m&put)==m)
        {
            cr=(cn*cr);
            cr%=9973;

        }
         cn=(cn*cn);
         cn%=9973;
    }
    return cr;
}





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;
        while(nr%v[i]==0){d++;nr/=v[i];}
        cp=(ridic(v[i],d)-1)%9973;
        cp2=ridic(v[i]-1,9971)%9973;


        dv=(long long)(d*dv)%9973;
        sum=(sum%9973)*(cp%9973)*(cp2%9973)%9973;
    }
    if(nr>1)
    {
        dv=(dv*2)%9973;
        sum=((sum%9973)*((nr+1)%9973))%9973;
    }
    fprintf(g,"%lld ",dv);
    fprintf(g,"%lld\n",sum);
}



int main()
{
    b=0;

    fscanf(f,"%d",&a);
    for(i=1;i<=a;i++)
    {
        fscanf(f,"%lld",&w[i]);
        if(w[i]>mx)mx=w[i];

    }
    mx2=trunc(sqrt(mx));
    ciur();

    for(i=1;i<=a;i++)
    {
         nr=w[i];
         if(nr==1) fprintf(g,"%d %d\n",1,1);
         else if(nr<1000000 && prim[nr]==0 && (nr%2))
              fprintf(g,"%d% lld\n",2,(nr+1)%9973);
         else desc();
    }


    fclose(g);
    return 0;
}