#include<cstdio>
#include<bitset>
#include<vector>
#include<utility>
#define M 9973
using namespace std;
vector<int> prime;
vector< pair<int,int> > desc;
bitset<500005> P;
int n;
void descompunere()
{
    int k;
    vector<int>::iterator it=prime.begin();
    for(;n!=1&&it!=prime.end();it++)
    {
        k=*it;
        if(n%k==0)
        {
            desc.push_back(make_pair(k,0));
        }
        for(;n%k==0;desc.back().second++,n/=k);
    }
    if(n!=1) desc.push_back(make_pair(n,1));
}
void divizori()
{
    int s=1,k;
    vector< pair<int,int> >::iterator it=desc.begin();
    for(;it!=desc.end();it++)
    {
        k=(*it).second;
        s=s*(k+1);
    }
    printf("%d ",s);
}
int putere(int p,int k)
{
    int o=p,i,s=1;
    for(i=k;i;i>>=1)
    {
        if(i&1)
        {
            s*=o;
            s%=M;
        }
        o*=o;
        o%=M;
    }
    return s;
}
void invmod(int a,int b,int *x,int *y)
{
    if(b==0)
    {
        *x=1;
        *y=0;
        return;
    }
    else
    {
        int x0,y0;
        invmod(b,a%b,&x0,&y0);
        *x=y0;
        *y=x0-(a/b)*y0;
    }
}
void suma()
{
    int s=1,k,p,x,y;
    vector< pair<int,int> >::iterator it=desc.begin();
    for(;it!=desc.end();it++)
    {
        p=(*it).first;
        k=(*it).second;
        invmod(p-1,M,&x,&y);
        for(;x<0;x+=M);
        s=(s*((putere(p,k+1)-1)*x%M))%M;
    }
    printf("%d ",s);
}
void golire()
{
    for(;!desc.empty();desc.pop_back());
}
int main()
{
    int i,j,t;
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
    scanf("%d",&t);
    prime.push_back(2);
    for(i=1;i<=500000;i++)
    {
        if(!P[i])
        {
            prime.push_back(2*i+1);
            for(j=3*i+1;j<=500000;j+=2*i+1) P[j]=1;
        }
    }
    for(;t;t--)
    {
        scanf("%d",&n);
        descompunere();
        divizori();
        suma();
        golire();
        printf("\n");
    }
    return 0;
}