#include<bits/stdc++.h>
#define int long long
#define MOD 9973
using namespace std;

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

int nou,ciur[1000005],prime[1000005],k;

struct cv
{
    int nr,div;
}v[1000004];

void descomp(int x)
{
    int e=0;
    while(x%2==0)
    {
        x/=2;
        e++;
    }
    if(e!=0)
    {
        nou++;
        v[nou].div=e;
        v[nou].nr=2;
    }
    for(int i=3; i<=k && 1LL*prime[i]*prime[i]<=x; i+=2)
    {
        if(x%i==0)
        {
            e=0;
            while(x%i==0)
            {
                x/=i;
                e++;
            }
            if(e!=0)
            {
                nou++;
                v[nou].div=e;
                v[nou].nr=i;
            }
        }
    }
    if(x!=1)
    {
        nou++;
        v[nou].div=1;
        v[nou].nr=x;
    }
}

int pow_log(int a, int b)
{
    int sol=1;
    while(b!=0)
    {
        if(b%2==1)
        {
            sol*=a;
            sol%=MOD;
        }
        a*=a;
        a%=MOD;
        b/=2;
    }
    return sol;
}

signed main()
{
    int t,l,n,i,nrdiv,sum,val,prod,j;
    ciur[0]=ciur[1]=1;
    for(i=1;i<=1000000;i++)
    {
        if(ciur[i]==0)
        {
            k++;
            prime[k]=i;
            for(j=2*i;j<=1000000;j+=i)
                ciur[i]=1;
        }
    }
    f>>t;
    for(l=1;l<=t;l++)
    {
        f>>n;
        nou=0;
        nrdiv=0;
        prod=1;
        int nrdiv1=1;
        descomp(n);
        for(i=1;i<=nou;i++)
        {
            nrdiv=0;
            nrdiv+=(v[i].div+1);
            nrdiv1*=nrdiv;
            val=pow_log(v[i].nr,v[i].div+1);
            val--;
            val*=pow_log(v[i].nr-1,MOD-2);
            prod*=val;
            prod%=MOD;
        }
        g<<nrdiv1<<" ";
        g<<prod<<'\n';
    }
    return 0;
}