#define MOD 9973
#include <cstdio>

using namespace std;

long long t, x, nrdiv=1, s;
char ciur[1000002];
long long a[100000], nr;
void c()
{
    ciur[1] = '1';
    for(int i=2; i<=1000002; i++)
    {
        if(ciur[i] == 0)
        {
            for(int j=i+i; j<=1000002; j+=i)
                ciur[j] = '1';
            a[nr++] = i;
        }
    }
    nr--;
}


void sumadiv(long long n, long long p, long long &psus)
{

    long long rez=1;
    while(p > 0)
    {
        if(p%2 == 1)
        {
            p--;
            rez=(rez*n)%MOD;
        }
        n=(n*n)%MOD;
        p/=2;
    }
    while(rez<=0)
        rez+=MOD;

    psus=(psus*(rez-1))%MOD;
}

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

}
int main()
{
    freopen("ssnd.in", "r", stdin);
    freopen("ssnd.out", "w", stdout);
    c();
    long long u=0;
    long long n;
    scanf("%lld", &n);
    for(int i=1; i<=n; i++)
    {
        long long pjos=1, psus=1;
        nrdiv=1;
        long long x=0, y=0;
        scanf("%lld", &u);
        long long e=0;
        for(int j=0; a[j]*a[j] <= u; j++)
        {
            if(u%a[j] == 0)
            {
                e=0;
                while(u%a[j] == 0)
                {
                    e++;
                    u/=a[j];
                }
                nrdiv=nrdiv*(1+e)%MOD;
                pjos=(pjos*(a[j]-1))%MOD;
                sumadiv(a[j], e+1, psus);
            }
        }
        if(u!=1)
        {
            nrdiv=nrdiv*2%MOD;
            pjos=(pjos*(u-1))%MOD;
            sumadiv(u, 2, psus);
        }
        euclid(pjos, MOD, x, y);
        while(x < 0)
            x+=MOD;
        printf("%lld ", nrdiv);
        printf("%lld\n", (psus*x)%MOD);

    }
    return 0;
}