#include <iostream>
#include <fstream>
#include <vector>
#define mod 9973
using namespace std;

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

vector<long long>prime;


long long n, x, numar,inm, suma=1;
long long lungime;
bool ciur[1000005];

///s=1*(2^n-1)/2-1

void ciur_fct()
{
    ciur[0]=1;
    ciur[1]=1;
    for (long long i=2; i<=1000000; i++)
    {
        if (!ciur[i])
        {
            prime.push_back(i);
            long long mult=2*i;
            while (mult<=1000000)
                ciur[mult]=1,mult+=i;
        }
    }
}

long long ridicare_putere(long long x, long long nr)
{
    long long st=1, dr=x;
    while (nr)
    {
        if (nr%2==0)
        {
            dr=dr*dr;
            dr%=mod;
            nr/=2;
        }
        else
        {
            st*=dr;
            st%=mod;
            nr--;
        }
    }
    return st;
}

void invers_mod(long long a, long long b, long long &k, long long &l)
{
    if (b==0)
    {
        k=1;
        l=0;
        return;
    }
    long long kp, lp;
    invers_mod(b,a%b,kp,lp);
    k=lp;
    l=kp-lp*(a/b);

}

long long prog_geom(long long x, long long nr)
{
    long long sus=ridicare_putere(x,nr)-1;
    if (sus<0)
        sus+=mod;
    long long jos=(x-1)%mod;
    if (jos<0)
        jos+=mod;
    long long k, p;
    if (jos==0)
        return nr%mod;
    invers_mod(jos,mod, k, p);
    if (k<0)
        k+=mod;
    return (sus*k)%mod;
}

long long numar_div(long long val)
{
    numar=1;
    for (long long i=0; i<lungime; i++)
    {
        if (prime[i]*prime[i]>val)
            break;
        inm=0;
        while (val%prime[i]==0)
        {
            val/=prime[i];
            inm++;
        }
        if (inm)
        {
            suma=suma*prog_geom(prime[i],inm+1);
            suma%=mod;
        }
        numar*=(inm+1);

    }
    if (val>1)
    {
        numar*=2;
        suma*=(val+1);
        suma%=mod;
    }
    return numar;
}

int main()
{
    ciur_fct();
    f >> n;
    lungime=prime.size();
    for (int i=1; i<=n; i++)
    {
        suma=1;
        f >> x;
        g << numar_div(x) <<' ';
        g << suma <<'\n';

    }
    return 0;
}