#include<fstream>
#include<cmath>
#define NMAX 1000010
#define MOD 9973

using namespace std;

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

int nr, sum;
//long long x;
bool ciur[NMAX];

void Ciur()
{
    int i,j;
    for (j=4; j<NMAX; j+=2) ciur[j]=1;
    for (i=3; i<NMAX; i+=2)
    if (!ciur[i])
        for (j=i+i+i; j<NMAX; j+=i+i) ciur[j]=1;
}

int div(int p, long long &x)
{
    int nr=1;
    while (x%p==0) x/=p, ++nr;
    return nr;
}

void Solve(long long &x)
{
    int d, rad=sqrt((double)x);
    long long aux=x;
    sum=(1+x)%MOD; nr=1;
    for (d=2; (long long)d*(long long)d<=aux; ++d)
        if (aux%d==0)
        {
            sum=(sum+d+aux/d)%MOD;
            if (!ciur[d]) nr*=div(d, x);
        }
    if (rad*rad==aux)
    {
         sum=(sum+MOD-rad)%MOD;

    }
    else if (x>1) nr*=2;
}

void Citeste()
{
    int t;
    long long x;
    f>>t;
    while (t--)
    {
        f>>x;
        Solve(x);
        g<<nr<<" "<<sum<<"\n";
    }
}

int main()
{
    Citeste();
    f.close();
    g.close();
    return 0;
}