#include<iostream>
#include<fstream>

using namespace std;
void fun(long long n,long long &nr,long long &s)
{long long i;
s=n+1;
nr=2;
for(i=2;i<=n/2;i++)
    if(n%i==0)
    {
        s=s+i;
        nr++;}
}


int main()
{
    ifstream f("ssnd.in");
    ofstream g("ssnd.out");
    long long n,x,s,nr,vec[10001],i=2,c;
    f>>n;
    for(i=1;i<=10000;i++)
    vec[i]=0;
    i=2;
    while(i<=10000)
    {
        if(vec[i]==0)
        {
            c=i+i;
            while(c<=10000)
            {
                vec[c]=1;
                c=c+i;
            }
        }
        i++;
    }
    while(n)
    {
        f>>x;
        if(vec[x]==1||x>10000)
       {

        fun(x,nr,s);
        g<<nr<<" "<<s%9973<<"\n";
       }
       else
       g<<2<<" "<<(x+1)%9973;
        n--;
    }

    f.close();
    g.close();
    return 0;
}