#include <fstream>
#define mod 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int a[1000005],prime[1000005],k,y,n,e,nrdiv,t,f[20],nrf,nrd,d,expo[20];
long long nr;
void Ciur()
{
    int i,j;
    a[1]=1;
    k=0;
    for(i=4;i<=1000005;i=i+2)a[i]=1;
    for(i=3;i*i<=1000005;i=i+2)
        if(a[i]==0)
    for(j=i*i;j<=1000005;j=j+2*i)a[j]=1;
    prime[1]=2;
    k=1;
    for(i=3;i<=1000005;i=i+2)
        if(a[i]==0)
        prime[++k]=i;
}
void NrDiv(long long n)
{
    nrf=0;
    nrd=1;
    d=2;
    int i=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=prime[++i];
    }
    if(n>1){
        f[++nrf]=n;
        nrd*=2;
        expo[nrf]=2;
    }
}
int Rid(int b, int x)
{
    int prod = 1;
    while(x != 0)
    {
        if(x % 2 == 1)
        {
            x--;
            prod = (1LL * b * prod)%mod;
        }
        x/=2;
        b=(1LL*b*b)%mod;
    }
    return prod;
}
void Sum(int numere)
{
    long long sum = 1, y;
    long long i, em, fa;
    for(i = 1; i<= nrf; i++)
    {
        fa = f[i];
        em = expo[i];
        y =Rid(fa, em)%mod;
        y--;
        if(y==-1)
            y=9972;
        sum =(1LL*sum*y)%mod;
        sum =(1LL*sum*(Rid(fa-1, mod-2)%mod))%mod;
    }
    fout << sum <<"\n";
}
int main(){
    Ciur();
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        fin>>nr;
        NrDiv(nr);
        fout<<nrd<<" ";
        Sum(nrf);
    }
    return 0;
}