#include<bits/stdc++.h>
#define infinit 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
bitset<1000005>a;
int n,k,prime[90000],f[20],cnt;
int expo[20];
int nrd,teste;
void Ciur()
{
    int i,j;
    a[1]=1;
    k=0;
    for(i=4;i<=1000000;i=i+2)a[i]=1;
    for(i=3;i*i<=1000000;i=i+2)
        if(a[i]==0)
    for(j=i*i;j<=1000000;j=j+2*i)a[j]=1;
    prime[1]=2;
    k=1;
    for(i=3;i<=1000000;i=i+2)
        if(a[i]==0)
        prime[++k]=i;
}
int Reinitializare()
{
    int i;
    for(i=1;i<=20;i++)
        f[i]=expo[i]=0;
}
int Putere(int xs,int ys)
{
    int prod=1;
    while(ys>0)
    {
        if(ys%2==1)
        {
            prod=(xs*prod)%infinit;
            ys--;
        }
        ys=ys/2;
        xs=(xs*xs)%infinit;
    }
    return prod;
}
int Putere1(int xs,int ys)
{
    int prod=1;
    while(ys>0)
    {
        if(ys%2==1)
        {
            prod=(xs*prod);
            ys--;
        }
        ys=ys/2;
        xs=(xs*xs);
    }
    return prod;
}
void Nrsum()
{
    int i,p,y;
    long long x=1;
    for(i=1;i<=cnt;i++)
    {
        p=f[i]-1;
        y=Putere1(f[i],expo[i]);
        y--;
        if(y==(-1))
            y=9972;
        x=1LL*x*(y%infinit)*(Putere(p,9971))%infinit;
    }
    fout<<x%infinit<<"\n";
}
void Nrdiv(long long n)
{
    int d,i,s;
    nrd=1;
    i=1;
    d=prime[i];
    while(n>1 and d*d<=n and i<=k)
    {
        s=0;
        if(n%d==0)
        {
            f[++cnt]=d;
            while(n%d==0)
            {
                s++;
                n=n/d;
            }
        nrd=nrd*(s+1);
        expo[cnt]=s+1;
        }
        i++;
        d=prime[i];
    }
    if(n>1)
    {
        nrd=nrd*2;
        f[++cnt]=n;
        expo[cnt]=2;
    }
    fout<<nrd<<" ";
}
int main()
{
    int i;
    long long numar;
    Ciur();
    fin>>teste;
    for(i=1;i<=teste;i++)
    {
        fin>>numar;
        Nrdiv(numar);
        Nrsum();
        Reinitializare();
    }
}