#define MOD 9973
#include <cstdio>

using namespace std;

long long int t, x, nrdiv=1, s;
char ciur[1000002];
long long int 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 int n, long long int p, long long int &psus)
{

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

void euclid(long long int a, long long int b, long long int &x, long long int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    long long int 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 int u=0;
    long long int n;
    scanf("%lld", &n);
    for(int i=1; i<=n; i++)
    {
        long long int pjos=1, psus=1;
        nrdiv=1;
        long long int x=0, y=0;
        scanf("%lld", &u);
        int 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);
                pjos=(pjos*(a[j]-1))%MOD;
                sumadiv(a[j], e+1, psus);
            }
        }
        if(u != 1)
        {
            nrdiv=nrdiv*2;
            pjos=(pjos*(u-1))%MOD;
            sumadiv(u, 2, psus);
        }


        euclid(pjos, MOD, x, y);
        while(x < 0)
            x+=MOD;
        printf("%d ", nrdiv);
        printf("%d\n", (psus*x)%MOD);
        // }

    }
    return 0;
}