#include <bits/stdc++.h>

using namespace std;
ofstream fout ("ssnd.out");

bitset <1000007> bit;
int prim[80000], k;
int expo[20], f[20], nrf;

void Ciur()
{
    int i, j;
    for (i=4; i<=1000000; i+=2)
        bit[i]=1;
    for (i=3; i*i<=1000000; i+=2)
        if (bit[i]==0)
            for (j=i*i; j<=1000000; j=j+2*i)
                bit[j]=1;
    k=0;
    prim[++k]=2;
    for (i=3; i<=1000000; i+=2)
        if (bit[i]==0)
            prim[++k]=i;
}

int NrDiv(long long n)
{
    int d, e, i, nrd;
    i=1;
    nrf=0;
    nrd=1;
    d=prim[1];
    while (n>1 && d*d<=n && i<=k)
    {
        if (n%d==0)
        {
            f[++nrf]=d;
            e=0;
            while (n%d==0)
            {
                e++;
                n/=d;
            }
            nrd*=(e+1);
            expo[nrf]=(e+1);
        }
        d=prim[++i];
    }
    if (n>1)
    {
        f[++nrf]=n;
        nrd*=2;
        expo[nrf]=2;
    }
    return nrd;
}

int RidicP(int y, int x, int p)
{
    int prod=1;
    while (x!=0)
    {
        if (x%2==1)
        {
            prod=(1LL*prod*y)%p;
            x--;
        }
        y=(1LL*y*y)%p;
        x/=2;
    }
    return prod;
}

void Suma()
{
    int i;
    long long s=1;
    for (i=1; i<=nrf; i++)
    {
        s*=(1LL * (RidicP(f[i], expo[i], 9973)-1) * RidicP((f[i]-1), 9971, 9973))%9973;
    }
    fout << s << "\n";
}

void Citire()
{
    ifstream fin ("ssnd.in");
    int t, i, m;
    long long x;
    fin >> t;
    for (i=1; i<=t; i++)
    {
        fin >> x;
        m=NrDiv(x);
        fout << m << " ";
        Suma();
    }
    fin.close();
}

int main()
{
    Ciur();
    Citire();
    fout.close();
    return 0;
}