#include <iostream>
#include <fstream>
#define MOD 9973
using namespace std;

bool a[1000500];
long long int prim[100000];
long long int n, m;
int nrdiv = 1, s = 1;

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

void fciur()
{
    int k = 0;
    for (int i=2;i*i<=1000000;i++)
        if (a[i] == 0)
            for (int j=i;j<=1000000/i;j++)
                a[i*j]=1;
    for (int i=2;i<=1000000;i++)
        if (a[i] == 0)
        {
            prim[k] = i;
            k++;
        }
    prim[k] == m*2;
}

void put(long long int pr, long long int p, long long int &rez)
{
    if(p == 0)
        return;
    if(p % 2 != 0)
    {
        rez = (pr*rez) % MOD;
        p--;
    }
    else
    {
        p /= 2;
        pr = (pr*pr) % MOD;
    }
    put(pr,p,rez);
}

void inversmodular(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    inversmodular(b, a%b, x1, y1);
    x = y1;
    y = x1 - a/b * y1;
}

void div()
{
    int e;
    int aux;
    for(int j = 0; j<n; j++)
    {
        f>>m;
        aux = m;
        for(int i = 0; prim[i] <= m; i++)
        {
            e = 0;
            while(aux%prim[i]==0)
            {
                aux/=prim[i];
                e++;
            }
            if(e!=0)
            {
                int invmod = 0, l = 0;
                long long int rez = 1;
                put(prim[i], e + 1, rez);
                inversmodular((prim[i] - 1)%MOD, MOD, invmod, l);
                while(invmod < 0)
                    invmod+=MOD;
                s *= (((rez - 1) % MOD) * invmod) % MOD;
            }
            nrdiv = nrdiv * (1+e);
        }
        g<<nrdiv<<" "<<s<<"\n";
        nrdiv = 1;
        s = 1;
    }
}


int main()
{
    f>>n;
    fciur();
    div();
    return 0;
}