#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
long long int i,j,s,n,a,d;
char v[62510];
int main()
{
    fin>>n;
    for(i=3;i<1000000;i+=2)
    {
        if(!(v[i/16]&(1<<(i%16/2+1))))
            for(j=i*3;j<1000000;j+=2*i)
                 v[j/16]=v[j/16]| 1<<(j%16/2+1);
    }
    for(i=1;i<=n;i++)
    {
        fin>>a;s=0;d=0;
        if(!(v[a/16]&(i<<(i%16/2+1)))&&a%2)
            fout<<2<<" "<<a+1<<'\n';
        else
            {for(j=1;j<=sqrt(a);j++)
        {
            if(a%j==0)
            {
                d++;
                s+=j;s+=a/j;
                if(a/j!=j)
                {d++;}
                s=s% 9973;
            }
        }if(a==2){d=2;s=3;}
        fout<<d<<" "<<s% 9973<<'\n';}
    }
    return 0;
}