#include <iostream>
#include<fstream>
#include<math.h>
using namespace std;

    ifstream f("ssnd.in");
    ofstream g("ssnd.out");

void fun(long long a,long long &nr,long long &s)

{

nr=s=1;
long long baza[1000],exp[1000],i=2,c=0;
for(i=1;i<=998;i++)
    exp[i]=0;
i=2;
while(a!=1)
{
    if(a%i==0)
    {
        c++;
        baza[c]=i;
        while(a%i==0)
        {
            exp[c]++;
            a=a/i;
        }
    }
    i++;
}



long long p=1;
for(i=1;i<=c;i++)
{
    nr=nr*(exp[i]+1);
    p=pow(baza[i],(exp[i]+1));
    s=s*(p-1)/(baza[i]-1);}


}


int main()
{
    long long n,i,nr,s,v[1001],num[100001],max,c;

    f>>n>>v[1];
    max=v[1];
    for(i=2;i<=n;i++)
    {
            f>>v[i];
            if(max<v[i])
                max=v[i];
    }
    for(i=1;i<=99998;i++)
        num[i]=0;
    for(i=2;i<=max;i++)
    {
        if(num[i]==0)
        {
            c=i+i;
            while(c<=max)
            {
                num[c]=1;
                c=c+i;
            }
        }
    }
for(i=1;i<=n;i++)
    if(num[v[i]]==0)
        g<<2<<" "<<(v[i]+1)%9973<<endl;
    else

    {
        fun(v[i],nr,s);
        g<<nr<<" "<<s%9973<<endl;
    }
    f.close();
    g.close();
    return 0;
}