#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

int t;
long long int n;
bool a[1000003];
ifstream fin("ssnd.in");
ofstream fout("ssnr.out");

void reini()
{
    for(int i=0;i<1000000;i++)a[i]=0;

}

int main()
{

    fin>>t;
    for(int i=0;i<t;i++){

    fin>>n;
    long int sum=1+n, nr=2;
    if(n%2==0)
        {
            nr+=2;
            sum+=2+n/2;
        }

    for(int i=3;i<=n;i+=2)
        if(!a[i])
        {

        for(int j=i+i;j<=n;j+=i)
        {
            a[j]=1;
            if(j==n)nr+=2,sum+=i+n/i;
        }
        }

    fout<<nr<<" "<<sum%9973;

    }
    return 0;
}