#include <cstdio>
#include <vector>
#include <bitset>

#define Lim 1000400
#define Cmx 1000300
#define MOD 9973

using namespace std;
int T;
long long X;
bitset<Lim> ciur;
vector<int> is_prime;
vector<int> divi;
vector<int> prim;

void precalc()
{
    is_prime.push_back(2);
    for(int i = 1; ((i<<1)|1) <= Cmx; ++i)
        if(!ciur[(i<<1)|1])
        {
            is_prime.push_back((i<<1)|1);
            for(int j = 1; ((j<<1)|1)*((i<<1)|1) <= Cmx; ++j)
                ciur[((j<<1)|1)*((i<<1)|1)] = 1;
        }
}

void euclid(long long a,long long b,long long &x, long long &y)
{
    if(!b){
        x = 1;
        y = 0;
        return;
    }
    long long x1,y1;
    euclid(b,a%b,x1,y1);
    x = y1;
    y = x1 - (a/b)*y1;
}

void descomp(long long val)
{
    divi.clear();
    prim.clear();
    for(int i = 0; is_prime[i]*is_prime[i] <= val; ++i)
    {
        int dd = 0;
        int x = is_prime[i];
        while(val%is_prime[i] == 0)
        {
            ++dd;
            val /= is_prime[i];
        }
        if(dd)
        {
            divi.push_back(dd);
            prim.push_back(is_prime[i]);
        }
    }
    if(val > 1)
    {
        divi.push_back(1);
        prim.push_back(val);
    }
}

long long lg_put(long long a,long long b)
{
    long long x1 = a,x2 = 1;
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    while(b > 1)
        if(b & 1){
            x2 = ( x1 * x2 )% MOD;
            b ^= 1;
        }
        else{
            x1 = ( x1 * x1 )% MOD;
            b>>=1;
        }
    return ( x1 * x2 )%MOD;
}

void get_nr()
{
    long long rez = 1;
    for(int i = 0; i <(int)divi.size(); ++i)
        rez = rez *(1LL*divi[i] + 1);
    printf("%lld ",rez);
}

void get_sum()
{
    long long x1,y1;
    long long rez = 1;
    long long v1,v2;
    for(int i = 0; i < (int)divi.size(); ++i)
    {
        v1 = prim[i];
        v2 = divi[i] + 1;
        rez = rez * (lg_put(v1,v2) - 1);
        euclid(v1-1,MOD,x1,y1);
        rez = (rez * x1) % MOD;
    }
    printf("%lld",(rez+MOD)%MOD);

}

int main()
{
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);

    precalc();
    scanf("%d",&T);
    for(int tst = 1; tst <= T; ++tst)
    {
        scanf("%lld",&X);
        descomp(X);
        get_nr();
        get_sum();
        printf("\n");
    }

    return 0;
}