#include <stdio.h>
#define lim 1000001
#define MOD 9973
unsigned int v[100500];
char ciur[lim];
long long p,nr,x,y;
long long ridicput(int baza,int exp){
    long long p=1;
    while(exp>0){
        if(exp%2==1){
            p=(p*baza)%MOD;
            exp--;
        }
        baza=(baza*baza)%MOD;
        exp/=2;
    }
    return p;
}
int verif(int div,int n){
    long long p1,p2;
    int put=0;
    while(n%div==0){
        put++;
        n/=div;
    }
    p1=(ridicput(div,put+1)-1)%MOD;
    p2=ridicput(div-1,MOD-2)%MOD;
    p=(((p*p1)%MOD)*p2)%MOD;
    nr=nr*(put+1);
    return n;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("ssnd.in","r");
    fout=fopen("ssnd.out","w");
    int i,j,n;
    for(i=2;i*i<lim;i++)
        if(ciur[i]==0)
            for(j=i*i;j<lim;j+=i)
                ciur[j]=1;
    j=0;
    for(i=2;i<=lim;i++)
        if(ciur[i]==0){
            j++;
            v[j]=i;
        }
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(fin,"%I64d",&x);
        p=1;
        nr=1;
        y=x;
        j=1;
        while((long long)v[j]*v[j]<=x){
            y=verif(v[j],y);
            j++;
        }
        if(y>1)
            y=verif(y,y);
        if(p==1){
            p=p+x;
            nr=2;
        }
        fprintf(fout,"%I64d %I64d\n",nr,p);
    }
    fclose(fin);
    fclose(fout);
return 0;
}