#include <bits/stdc++.h>
#define p 9973

using namespace std;

bitset<1000002>a;
int prime[200008], expo[20], f[20],nrf, t, k;

ifstream fin("ssnd.out");
ofstream fout ("ssnd.out");

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

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

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

}

void SumDiv()
{
    long long sum = 1, y;
    long long i, e, fa;
    for(i = 1; i<= nrf; i++)
    {
        fa = f[i];
        e = expo[i];
        y = Rid(fa, e) % p;
        y--;
        if(y == -1)
            y=9972;
        sum =(1LL * sum * y) % p;
        sum =(1LL * sum * (Rid(fa - 1, p - 2) % p)) % p;
    }
    fout << sum <<"\n";
}

int main()
{
    ifstream fin ("ssnd.in");
    Ciur();
    long long i, x;
    fin >> t;
    for(i = 1; i<=t; i++)
    {
        fin >> x;
        fout << NrDiv(x) << " ";
        SumDiv();

    }
    return 0;
}