#include <fstream>
#include <iostream>
#include <cmath>
#define modulo 9973;
using namespace std;
long long sumdiv(long long n)
{
long long d=2,p=0,s=1,baza=1,exponent=1,suma,x;
while(n>1)
{
    p=0;
    while(n%d==0)
    {
        p++;
        n=n/d;
    }
    if(p>0)
    {
        x=pow(d,p+1);
        s=s*(x-1);
        baza=baza*(d-1);
    }
    if(d==2)
        d++;
    else
        d=d+2;
    if(n>1 && d*d>n)
        d=n;
    suma=(s/baza)%modulo;

}
return suma;
}
long long nrdiv(int n)
{
    long long d=2,p=0,x=1;
    while(n>1)
    {
        p=0;
        while(n%d==0)
        {
            p++;
            n=n/d;
        }
        if(p>0)
            x=x*(p+1);
        if(d==2)
            d++;
        else
            d=d+2;

        if(n>1 && d*d>n)
            d=n;
    }
    return x;
}
int main()
{
long long n,i,x,y;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
f>>n;
for(i=0;i<n;i++)
{
    f>>x;
    y=nrdiv(x);
    if(y==2)
        g<<2<<" "<<x+1<<"\n";
    else

  g<<y<<" "<<sumdiv(x)<<"\n";

}

    return 0;
}