#include <cstdio>
#include <iostream>
 char ciur[250001];
using namespace std;


int ciurr (int n)
{
    FILE *f=fopen("ciur.in","r");
    int nc,i,np=0,ind;

    nc=2;
    while(1)
    {
        while((ciur[nc/8]&(1<<(nc%8)))!=0 && nc<=n)nc++;

        i=2;
        while(i*nc<=n)
        {
            ind=i*nc;
            ciur[ind/8]=ciur[ind/8]|(1<<(ind%8));
            i++;
        }
         if(nc==n) return 1; if(nc>n) return 0;
        np++;
        nc++;

    }

    return np;
}

int main()

{
    int n;
     FILE *f=fopen("ssnd.in","r"),*g=fopen("ssnd.out","w");
   fscanf(f,"%d",&n);
   int v[100];
   for(int i=1;i<=n;i++)
    {
        fscanf(f,"%d",&v[i]);
    }

    for(int i=1;i<=n;i++)
    {
        if(ciurr(v[i])==0)
        {

       int nr=2;
       long long sum=1+v[i];
       for(int d=2;d<=v[i]/2;d++)
       {
           if(v[i]%d==0) nr++,sum=sum+d;

       }
    sum=sum%9973;
     fprintf(g,"%d %d\n",nr,sum);

        }


        else fprintf(g,"2 %d\n",(v[i]+1)%9973);

    }
    return 0;
}